Wait for it

Given $N$, $A$ and $B$, find the value of the following expression: $$ \sum_{i=0}^{N} \sum_{j=0}^{N} \text{gcd}(A^i + B^i, A^j + B^j) $$ Since the value can be large, find it modulo $(10^9 + 7)$. ### Input - The first line of the input contains an integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - Each test case consists of a single line containing three