F. Find GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pt is a brilliant mathematician who has just discovered the power of the Euclidean algorithm for finding the GCD of two numbers. Excited to test her new knowledge, she shares her discovery with her friend, Kalu, who challenges her with a problem to solve. She needs your help to solve the problem.

The problem is to find the GCD of two numbers, $$$n$$$ raised to the factorials of $$$a$$$ and $$$b$$$, respectively, and then take the result modulo $$$1000000007$$$. In other words, you are given three integers: $$$a$$$, $$$b$$$, and $$$n$$$, and you must find the value of: $$$$$$ GCD(n^{a!},\; n^{b!}) \bmod{1000000007}$$$$$$

Input

The first line of input consists of an Integer $$$T$$$ $$$( 1 \le T \le 10^5)$$$ denoting the number of test cases. Each of the following T lines contains 3 integers $$$a$$$, $$$b$$$ and $$$n$$$ $$$(0\le a,\ b,\ n \le10^5)$$$.

Output

For each test case print the GCD in a separate line.

Example
Input
3
1 1 2
1 7 4
3 3 2
Output
2
4
64
Note

$$$GCD(p,\, q)$$$ denotes the greatest common divisor of $$$p$$$ and $$$q$$$.

$$$x!$$$ denotes factorial of $$$x$$$ i.e. $$$x! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot x$$$ (in particular, $$$0!=1$$$).

$$$a \text{ modulo } b$$$ (shortened $$$a \text{ mod } b$$$) is the only integer $$$c$$$, such that $$$0 \le c < b$$$ and $$$a - c$$$ is divisible by $$$b$$$.