Description

输入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的结果。

Input Format

第一行一个整数t表示数据组数。

接下来t组数据，每组数据为一行五个整数a,b,n,k,p，含义见题。

0<=a,b<p，1<=t<=1000,1<=n,p<=10^9,1<=k<=100。

Output Format

对于每组数据，输出一个整数表示答案。

1
0 1 2 2 1000

8