------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------

At ShareChat, there are are plenty of interesting problems to solve. Here is one of them.

Given integers $A$, $B$ and $N$, you should calculate the [GCD] of $A^{N} + B^{N}$ and $|A - B|$. (Assume that $GCD(0, a) = a$ for any positive integer $a$). Since this number could be very large, compute it modulo $1000000007$ ($10^{9} + 7$).

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $A$, $B$ and $N$.

------ Output ------
For each test case, print a single line containing one integer — the required GCD modulo $10^{9} + 7$.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ A, B, N ≤ 10^{12}$
$B ≤ A$

------ Subtasks ------
Subtask #1 (10 points): $1 ≤ A, B, N ≤ 10$

Subtask #2 (40 points): $1 ≤ A, B, N ≤ 10^{9}$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------
2
10 1 1
9 1 5
----- Sample Output 1 ------
1
2
----- explanation 1 ------
Example case 1: $GCD(10^{1} + 1^{1}, 10 - 1) = GCD(11, 9) = 1$

Example case 2: $GCD(9^{5} + 1^{5}, 9 - 1) = GCD(59050, 8) = 2$

见题面

见题面