You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

神奇数列

题目描述

神奇数列是指形如 $a_n=p\times a_{n-1} + (n-1)+q\times a_{n-2} + (n-2)$ 的数列。 今给定数列的两系数 $p$ 和 $q$，以及数列的最前两项 $a_1$ 和$a_2$，另给出两个整数 $n$ 和 $m$，试求数列的第 $n$ 项 $a_n \bmod m$。

输入格式

输入包含一行六个整数，$p,q,a_1,a_2,n,m$。

输出格式

输出包含一行一个整数表示答案。

样例 #1

样例输入 #1

1 1 1 1 10 7

样例输出 #1

4

提示

a[1] = 1

a[2] = 1

a[3] = 5

a[4] = 11

a[5] = 23

a[6] = 43

a[7] = 77

a[8] = 133

a[9] = 225

a[10] = 375

a[n] % m = 4

【数据范围】 对于 $100\%$ 的数据，$1\le p,q,a_1,a_2, n,m \le 10^{18}$。