#P1349. 广义斐波那契数列

广义斐波那契数列

题目描述

广义的斐波那契数列是指形如 an=p×an1+q×an2a_n=p\times a_{n-1}+q\times a_{n-2} 的数列。
今给定数列的两系数 ppqq,以及数列的最前两项 a1a_1a2 a_2,另给出两个整数 nnmm,试求数列的第 nnanmodma_n \bmod m

输入格式

输入包含一行六个整数,p,q,a1,a2,n,mp,q,a_1,a_2,n,m

输出格式

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

1 1 1 1 10 7

6

提示

数列第 1010 项是 555555mod7=655 \bmod 7 = 6

【数据范围】
对于 100%100\% 的数据,p,q,a1,a2[0,2311]p,q,a_1,a_2 \in [0,2^{31}-1]1n,m23111\le n,m \le 2^{31}-1