[Solution] Sherlock and Watson Gym Secrets Kick Start Session Solution

[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$A$, B$B$, and N$N$, and has asked Watson and Sherlock to pick two different positive integers i$i$ and j$j$, where i$i$ and j$j$ are both less than or equal to N$N$. Watson is expected to eat exactly iA$i^A$ sprouts every day, and Sherlock is expected to eat exactly jB$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$K$, then they get along well that day.

So, Watson and Sherlock need your help to determine how many such pairs of (i,j)$(i,j)$ exist, where i≠j$i\ne j$ and they get along well that day. As the number of pairs can be really high, please output it modulo 109+7(1000000007)${10}^9+7(1000000007)$.

Input

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Output

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

Limits

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

Test Set 1

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

Test Set 2

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