410432: GYM104021 D Easy Problem

A sequence $$$(a_{1},a_{2},\cdots,a_{n})$$$ is $$$(n,m,d)$$$-good if $$$1 \leq a_{i} \leq m~(1 \le i \le n)$$$ and $$$\gcd(a_{1},a_{2},\cdots,a_{n})=d$$$.

Given four integers $$$n$$$, $$$m$$$, $$$d$$$ and $$$k$$$, you are asked to calculate the sum of $$$f(q, k)$$$ for each $$$(n, m, d)$$$-good sequence $$$q$$$, where $$$f((a_{1},a_{2},...a_{n}),k) = (a_{1}a_{2} \cdots a_{n})^{k}$$$ for the sequence $$$q = (a_{1},a_{2},...a_{n})$$$.

Since the answer could be very large, you only need to output the answer modulo $$$59964251$$$.

The first line is an integer $$$T~(1 \leq T \leq 20)$$$, which is the number of test cases.

For each test case, the first line contains four integers $$$n~(1 \leq n \leq 10^{100000})$$$, $$$m~(1 \leq m \leq 100000)$$$, $$$d~(1 \leq d \leq 100000)$$$, $$$k~(1 \leq k \leq 10^9)$$$, which are described in the problem description.

For each test case, output a line containing a single integer.

1
3 3 3 1

27