Sherlock and Watson Gym Secrets (Large)

Watson and Sherlock are gym buddies.

Their gym trainer has given them three integers $A$, $B$, and $N$, and has asked them to pick two different positive integers $i$ and $j$, both less than or equal to $N$. Watson is expected to eat exactly $i^A$ sprouts every day, and Sherlock is expected to eat exactly $j^B$ sprouts every day.

Watson and Sherlock have noticed that if the total number of sprouts they eat on a given day is divisible by a certain integer $K$, they get along well that day.

Count the pairs $(i, j)$ with $i \ne j$ such that $i^A + j^B$ is divisible by $K$. Pairs are ordered, so $(1, 2)$ and $(2, 1)$ are different pairs. The number of pairs can be very large, so output it modulo $10^9+7$ ($1000000007$).

Since $i$ and $j$ are positive, $i^A = 1$ when $A = 0$, and $j^B = 1$ when $B = 0$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of one line with the four integers $A$, $B$, $N$, and $K$ described above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the required answer.

• $1 \le T \le 100$
• $0 \le A \le 10^6$
• $0 \le B \le 10^6$
• $1 \le K \le 100000$
• $1 \le N \le 10^{18}$

In the first test case of the example, the possible pairs are $(1, 2)$, $(1, 5)$, $(2, 1)$, $(2, 4)$, $(4, 2)$, $(4, 5)$, $(5, 1)$, and $(5, 4)$.

In the second test case, the possible pairs are $(1, 2)$, $(1, 3)$, and $(4, 1)$.

In the third test case, no pair is possible because of the condition $i \ne j$.