Problem Description

Watson and Sherlock are gym buddies.

Their gym trainer has given them three numbers, $A$, $B$, and $N$, and has asked Watson and Sherlock to pick two different positive integers $i$ and $j$, where $i$ and $j$ are 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 eaten by them on a given day is divisible by a certain integer $K$, then they get along well that day.

So, Watson and Sherlock need your help to determine how many such pairs of $(i, j)$ exist, where $i \neq j$. As the number of pairs can be really high, please output it modulo $10^9+7$ ($1000000007$).

Input Format

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 $4$ integers $A$, $B$, $N$ and $K$, as described above.

Output Format

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.

3
1 1 5 3
1 2 4 5
1 1 2 2

Case #1: 8
Case #2: 3
Case #3: 0

Hint

In Case $1$, the possible pairs are $(1, 2)$, $(1, 5)$, $(2, 1)$, $(2, 4)$, $(4, 2)$, $(4, 5)$, $(5, 1)$, and $(5, 4)$. In Case $2$, the possible pairs are $(1, 2)$, $(1, 3)$, and $(4, 1)$. In Case $3$, No possible pairs are there, as $i \neq j$.

Limits

$1 \le T \le 100$.

$0 \le A \le 10^6$.

$0 \le B \le 10^6$.

Small dataset (Test set 1 - Visible)

$1 \le K \le 10000$.

$1 \le N \le 1000$.

Large dataset (Test set 2 - Hidden)

$1 \le K \le 100000$.

$1 \le N \le 10^{18}$.