Your task is to find the n^th term of the following sequence :

F(n) = [F(n-1)*F(n-2)]^K for n>1

F(0), F(1), n and K will be provided as input. Modulus for all calculations is 1000000007. You should print the answer modulo 1000000007 i.e. F(n)%1000000007

Input

Input starts with a line containing an integer T ≤ 5000 which is the number of test cases in the file. Your program will be run on several input files.

Each test case consists of four space separated integers : F(0), F(1), n and K.

Output

T lines containing one integer each, corresponding to the answers for the T test cases.

Constraints

0 ≤ n ≤ 10¹⁸

0 ≤ K ≤ 10⁹

0 ≤ F(0), F(1) ≤ 10⁶

Example

Input:
1
1 1 2 1

Output:
1