Modular GCD

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$ de