Problem A: 特殊的数列

Problem A: 特殊的数列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 128  Solved: 22
[Submit] [Status] [Web Board] [Creator:]

Description

有一种特殊的数列,其生成规则如下:从第三项开始,每一项都等于前一项乘以系数 p 加上前前一项乘以系数 q 。具体来说,对于 n ≥ 3,有 an = p * an-1 + q * an-2

现在,给你数列的两个系数 p 和 q ,以及数列的前两项 a1 和 a。同时,还会给出两个整数 n 和 m 。你的任务是计算这个数列的第 n a,并将结果对 m 取模后输出。

Input

输入数据为一行,包含六个整数,依次为 p, q, a1, a2, n 和 m。 p, q, a1, a[0,2311], 1 ≤n, m≤ 2311。

Output

输出一个整数,即数列第 n 项 an 对 m 取模后的值。

Sample Input

1 1 1 1 10 7

Sample Output

6

HINT

数列第 10 项是 5555mod7=6