Little Cyan Fish 正在参加全国青少年钓鱼冬令营（WC）的算法讲座。在讲座中，一位神秘的讲师谈到了 Barrett 约减（Barrett reduction），这是一种由 P.D. Barrett 在 1986 年提出的约减算法。

为了检查你是否理解该算法的工作原理，Little Cyan Fish 给了你一个特殊的数字 $M$。然后，这位神秘的讲师定义了序列 $\{X\}$ 和 $\{Y\}$ 如下：

$$X_n = (\alpha \cdot X_{n-1} + X_{n-2} \cdot Y_{n-1}) \pmod M, n \ge 2$$

$$Y_n = (\beta \cdot Y_{n-1} + Y_{n-2} \cdot X_{n-1}) \pmod M, n \ge 2$$

现在，Little Cyan Fish 给了你 $\alpha, \beta, X_0, Y_0, X_1, Y_1, N$ 和 $M$ 的值。你的任务是计算 $\sum_{i=2}^{N} X_i$ 对 $M$ 取模的结果。

输入格式

输入的第一行包含八个整数 $\alpha, \beta, X_0, Y_0, X_1, Y_1, N$ 和 $M$ ($0 \le X_0, Y_0, X_1, Y_1, \alpha, \beta < M, 2 \le M \le 10^9, 2 \le N \le 10^8$)。

输出格式

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

样例

输入格式 1

114 514 1919 810 2024 112 154 12345678

输出格式 1

10095098