## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Sherlock and Watson Gym Secrets Kick Start Session Solution - Kick Start 2022

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 $\left(i,j\right)$ exist, where $i\ne j$ and they get along well that day. As the number of pairs can be really high, please output it modulo ${10}^{9}+7\left(1000000007\right)$.

### Input

The first line of the input gives the number of test cases, $T$$T$ test cases follow. Each test case consists of

Solution Click Below:-  👉
👇👇👇👇👇

one line with 4 integers $A$$B$$N$ and $K$, as described above.

### Output

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

### Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
$1\le \mathbf{T}\le 100$.
$0\le \mathbf{A}\le {10}^{6}$.
$0\le \mathbf{B}\le {10}^{6}$.

#### Test Set 1

$1\le \mathbf{K}\le {10}^{4}$.
$1\le \mathbf{N}\le {10}^{3}$.

#### Test Set 2

$1\le \mathbf{K}\le {10}^{5}$.
$1\le \mathbf{N}\le {10}^{18}$.