BZPRO
#5474. 线性递推数列
内存限制：512 MiB
时间限制：30 Sec
提交
提交记录
讨论
题目描述
输入5个整数a,b,n,k,p。
定义
g(0)=a,g(1)=b,g(i)=3g(i−1)−g(i−2)(i≥2)
换句话说g(n)相当于以a,b为初始值的一个线性递推数列。
f(n,0)=n,f(n,k)=f(g(n),k−1)(k≥1)
换句话说f(n,k)相当于把k个g函数嵌套使用 。
请输出f(n,k)modp的结果。
输入格式
第一行一个整数t表示数据组数。
接下来t组数据，每组数据为一行五个整数a,b,n,k,p，含义见题。
0≤a,b<p，1≤t≤1000,1≤n,p≤10^9,1≤k≤100。
输出格式
对于每组数据，输出一个整数表示答案。
样例
样例输入
1
0 1 2 2 1000
样例输出
8
数据范围与提示
BZPRO