广义斐波那契数列

题目描述

广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。 今给定数列的两系数 $p$ 和 $q$,以及数列的最前两项 $a_1$ 和 $ a_2$,另给出两个整数 $n$ 和 $m$,试求数列的第 $n$ 项 $a_n$ 对 $m$ 取模后的结果。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

1 1 1 1 10 7

输出样例 #1

6

说明

数列第 $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$。 --- $\text{upd 2023.8.23}$:新增加一组 Hack 数据。