Modular GCD problem of codechef

[zyan1zyan]

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≤1012
B≤A

Can anyone please give me the idea to solve this problem ??

[dhayden]

Google the properties of modulo arithmetic and see if you can figure out how to modify the standard GCD algorithm accordingly.