33OJ
登录 注册

#P17635. [ICPC 2019 Yinchuan R] Easy Problem

[ICPC 2019 Yinchuan R] Easy Problem

题目描述

称一个序列 (a1,a2,⋯ ,an)(a_{1},a_{2},\cdots,a_{n}) 是 (n,m,d)(n,m,d)-好的,如果 1≤ai≤m (1≤i≤n)1 \leq a_{i} \leq m~(1 \le i \le n) 且 gcd⁡(a1,a2,⋯ ,an)=d\gcd(a_{1},a_{2},\cdots,a_{n})=d。

给定四个整数 nn、mm、dd 和 kk,请你对于每一个 (n,m,d)(n, m, d)-好序列 qq,计算 f(q,k)f(q, k) 的总和,其中对于序列 q=(a1,a2,…,an)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}$。

由于答案可能非常大,你只需要输出答案对 5996425159964251 取模的结果。

输入格式

第一行是一个整数 T (1≤T≤20)T~(1 \leq T \leq 20),表示测试数据的组数。

对于每组测试数据,第一行包含四个整数 n (1≤n≤10100000)n~(1 \leq n \leq 10^{100000})、m (1≤m≤100000)m~(1 \leq m \leq 100000)、d (1≤d≤100000)d~(1 \leq d \leq 100000) 和 k (1≤k≤109)k~(1 \leq k \leq 10^9),含义如题目描述所述。

输出格式

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

1
3 3 3 1
27

提示

翻译由 DeepSeek V4 Pro 初步生成和 @greater_than 修缮完成