1042 - 数论：矩阵快速幂：广义斐波那契数列
Time Limit : 1 秒
Memory Limit : 256 MB
广义的斐波那契数列是指形如,其中n、n-1 、n-2为a的下标
an = p * an-1+ q * an-2
的数列。
今给定数列的两系数 p 和 q，以及数列的最前两项 a_1 和 a_2，另给出两个整数 n 和 m，试求数列的第 n 项 a_n 对 m 取模后的结果。
Input
输入包含一行六个整数，p,q,a_1,a_2,n,m。
Output
输出包含一行一个整数表示答案。
Examples
Input
1 1 1 1 10 7
Output
6
Hint
数列第 10 项是 55，55 \bmod 7 = 6。
【数据范围】
对于 100\% 的数据，p,q,a_1,a_2 \in [0,2^{31}-1]，1\le n,m \le 2^{31}-1。