P17635 [ICPC 2019 Yinchuan R] Easy Problem

称一个序列 $(a_{1},a_{2},\cdots,a_{n})$ 是 $(n,m,d)$-好的，如果 $1 \leq a_{i} \leq m~(1 \le i \le n)$ 且 $\gcd(a_{1},a_{2},\cdots,a_{n})=d$。 给定四个整数 $n$、$m$、$d$ 和 $k$，请你对于每一个 $(n, m, d)$-好序列 $q$，计算 $f(q, k)$ 的总和，其中对于序列 $q = (a_{1},a_{2},\ldots,a_{n})$，有 $f((a_{1},a_{2},\ldots,a_{n}),k) = (a_{1}a_{2} \cdots a_{n})^{k}$。 由于答案可能非常大，你只需要输出答案对 $59964251$ 取模的结果。

第一行是一个整数 $T~(1 \leq T \leq 20)$，表示测试数据的组数。 对于每组测试数据，第一行包含四个整数 $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)$，含义如题目描述所述。

对于每组测试数据，输出一行一个整数表示答案。

翻译由 DeepSeek V4 Pro 完成