最大公因数取模

【题目描述】

给定整数$A,B,N$,你需要计算$A^N + B^N$与$|A-B|$的最大公因数(特别地，我们定义$\gcd(0,a)=a$)。由于答案可能很大，请你计算答案对$1000000007(10^9+7)$取模的结果。

【输入格式】

输入的第一行包含一个整数$T$，代表测试数据的组数。接下来是$T$组数据。 每组数据仅有一行，包含三个整数$A$，$B$，$N$。

【输出格式】

对于每组数据，输出一行，包含一个整数，代表所求答案。

【样例输入】

2
10 1 1
9 1 5

【样例输出】

1
2

【数据规模与约定】

对于10%的数据有 $1 \le A,B,N \le 10$

对于50%的数据有 $1 \le A,B,N \le 10^6$

对于100%的数据有 $1\le T \le 10,1\le A,B,N \le 10^{12},B\le A$

【来源】

zrq