P17635 [ICPC 2019 Yinchuan R] 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.