eolymp
bolt
Try our new interface for solving problems

a^b^c

Time limit 1 second
Memory limit 128 MiB

Find the value of

a^{b^c} (mod~10^9 + 7)

Input data

The first line contains the number of test cases n. Each of the next n lines contains three numbers a, b, c~(a, b, c \le 10^9).

Output data

For each test case print in a separate line the value of a^{b^c} (mod~10^9 + 7).

Examples

Input example #1
3
3 7 1
15 2 2
3 4 5
Output example #1
2187
50625
763327764
Author Mykhailo Medvediev