当前没有测试数据。

题目描述

You are given four positive integers $x_0, x_1, a, b$. And you know $x_i = a \cdot x_{i-1} + b \cdot x_{i-2}$​ for all $i \ge 2$.

Given two positive integers n, and MOD, please calculate $x_n$​ modulo MOD.

Does the problem look simple? Surprise! The value of n may have many many digits!

输入格式

The input contains two lines. The first line contains four integers $x_0, x_1, a, b$ ($1 \le x_0, x_1, a, b \le 10^9$). The second line contains two integers n, MOD ($ 1 \le n < 10^{(10^6)}, 10^9 < MOD \le 2 \times 10^9 $, n has no leading zero).

输出格式

Print one integer representing the answer.

样例

样例输入 1

1 1 1 1
10 1000000001

样例输出 1

89

样例解释 1

The resulting sequence x is Fibonacci sequence. The 11-th item is 89.

样例输入 2

1315 521 20185 5452831
9999999999999999999999999999999999999 1000000007

样例输出 2

914730061