33OJ
登录 注册

#P17635. [ICPC 2019 Yinchuan R] Easy Problem

[ICPC 2019 Yinchuan R] Easy Problem

Problem Description

A sequence (a1,a2,⋯ ,an)(a_{1},a_{2},\cdots,a_{n}) is (n,m,d)(n,m,d)-good if 1≤ai≤m (1≤i≤n)1 \leq a_{i} \leq m~(1 \le i \le n) and gcd⁡(a1,a2,⋯ ,an)=d\gcd(a_{1},a_{2},\cdots,a_{n})=d.

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

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

Input Format

The first line is an integer T (1≤T≤20)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≤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), which are described in the problem description.

Output Format

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

1
3 3 3 1
27