B君的回忆(erinnerung)
题目描述
给定整数 a,b,定义下标为任意整数的序列 g:
$$g_0=a,\qquad g_1=b,\qquad g_i=3g_{i-1}-g_{i-2}\quad(i\ge2).$$
负下标通过反向递推唯一确定:
gi=3gi+1−gi+2(i<0).
再定义
fn,0=n,fn,k=fgn,k−1(k≥1).
嵌套计算中即使下标为负,也按上述定义求值。求 fn,k 对 p 取模的结果。
这里取模仅作用于最终结果,不改变整数序列本身的定义。
输入格式
第一行一个整数 T,表示数据组数。
接下来 T 行,每行五个整数 a,b,n,k,p。
输出格式
每组数据输出一行一个整数,位于 [0,p−1],表示答案。
样例
1
0 1 2 2 1000
8
样例解释
g2=3,g3=8,所以 f2,2=f3,1=f8,0=8。
数据范围
1≤T≤1000,0≤a,b<p,1≤n,p≤109,1≤k≤100。
其中20%的数据满足 k≤1,60%的数据满足 k≤2。
参考附件
原题资料(本页约定为准)