It is a simple maths problem.
You have to calculate (a^(b^c)) % M where a, c and M are positive numbers and b is defined as:
b = C(n,m) ,where C(n,r) is number of combinations of r objects taken from n objects.

Input:
First line of the input contains a single integer T denoting number of test cases.
For each test case, one line containing 5 space seperated intergers a, c, n, m, M.

Ouput:
For each test case, print a single line containing required number.

Constraints:

• 1<= T <=1020
• 1<= a,c,n,m <= 200000
• 1<= M <=1000000009
• m<=n

Sample Input:
3
2 3 2 1 7
5 3 4 3 5
2 3 6 3 83

Sample Output:
4
0
51