题目描述
称一个序列 (a1,a2,⋯,an) 是 (n,m,d)-好的,如果 1≤ai≤m (1≤i≤n) 且 gcd(a1,a2,⋯,an)=d。
给定四个整数 n、m、d 和 k,请你对于每一个 (n,m,d)-好序列 q,计算 f(q,k) 的总和,其中对于序列 q=(a1,a2,…,an),有 $f((a_{1},a_{2},\ldots,a_{n}),k) = (a_{1}a_{2} \cdots a_{n})^{k}$。
由于答案可能非常大,你只需要输出答案对 59964251 取模的结果。
输入格式
第一行是一个整数 T (1≤T≤20),表示测试数据的组数。
对于每组测试数据,第一行包含四个整数 n (1≤n≤10100000)、m (1≤m≤100000)、d (1≤d≤100000) 和 k (1≤k≤109),含义如题目描述所述。
输出格式
对于每组测试数据,输出一行一个整数表示答案。
1
3 3 3 1
27
提示
翻译由 DeepSeek V4 Pro 初步生成和 @greater_than 修缮完成