Problem2743--the reform and opening-up

2743: the reform and opening-up

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 121  Solved: 7
[Submit] [Status] [Web Board] [Creator:]

Description

改革春风吹满地~  Chinese people so niubi ~ (we are so niubi!)

某云飞是个很有钱的银,他喜欢把自己所有的钱都放在保险柜里。某天怪盗Zser潜入xyf家里,准备去盗取xyf所有的money,成为有钱人,从此走上人生巅峰(Zser:好嗨哦~),但是某云飞也是很聪明的,保险箱是个密码锁,上面写着

F(1) = A, F(2) = B,F(n) = F(n-1) * F(n-2) * CD(n > 2)

现在让求G(n)的值为多少(G(n)为F(n)的前n项积)

由于答案过大,所以G(n)%mod,且保留9位数字。不足则补0(毕竟某云飞家的密码锁还不够高级)

Input

第一行输入一个T表示测试组数(T <= 10000)

第二行输入六个正整数A,B,C,D,mod,n(1 <= A,B,C,D,mod,n <= 1e9)

Output

输出Zser算出来的九位数密码

Sample Input Copy

2
2 2 2 2 1000 3
3 3 3 3 3000 3

Sample Output Copy

000000064
000002187