J19 实践-2 广义斐波那契数列

题目描述

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

输入格式

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

输出格式

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

样例输入

1 1 1 1 10 7

样例输出

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$。