Background

Enhanced version link。

This is a math problem, but it was made by LMX for HQZ.

Problem Description

Define the multiplicative function $f(n)=(\mu \ast\operatorname{Id_2})(n)$.

Given $n,k$, you need to compute

$$\sum_{i_1\mid n}\sum_{i_2\mid i_1}\cdots\sum_{i_k\mid i_{k-1}}f(i_k)i_1i_k\mu^2\left(\dfrac{i_1}{i_k}\right)$$

Tips

$\mu$ denotes the Möbius function.

For $f$, we have $f(n)=\displaystyle \sum_{d\mid n}\mu(d)\left(\dfrac{n}{d}\right)^2$.

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$, the number of test cases.

Since $n$ is very large, we will give the standard prime factorization of $n=\displaystyle \prod_{i=1}^t p_i^{\alpha_i}$.

For each query, we first give two integers $k,m$.

The second line contains $t$, and the next $t$ lines each contain two integers $p_i,\alpha_i$.

(It is guaranteed that $p_i\ge p_{i-1}$ for $i\ge 2$, and $\alpha_i\ge 1$.)

Output Format

For each query, output one line: the answer modulo $m$.

5
3 998244353
3
3 2
5 1
7 1
4 1000000009
2
2 1
3 2
1 998244353
2
2 2
3 1
11451 191981012
11
2 1
3 1
5 1
7 1
11 1
13 1
17 1
19 1
23 1
29 1
31 1
514 520
2
2 10
3 10

189282114
124678
14965
82966193
260

Hint

For $100\%$ of the testdata, $T \le 20,n\le 10^{24},1\le k\le 10^6,m\le 1.14\times 10^9$.

Test Point ID	$n$	$k$	$T$	Special Property
$1$	$\le 80$	$\le 4$	$\le 5$	$N$
$2$	$\le 10^6$	$\le 10$
$3$	$\le 10^{12}$	$\le 20$	$\le 20$
$4$	$\le 10^{18}$	$\le 1$
$5$		$\le 10^3$
$6$		$\le 10^5$		$A$
$7$		$\le 10^6$		$B$
$8$	$\le 10^{24}$
$9$				$C$
$10\sim20$				$N$

Property $A$: It is guaranteed that $t\le 10$.

Property $B$: In the prime factorization $\displaystyle\prod_{i=1}^t p_i^{\alpha_i}$ of $n$, $\alpha_i=1$.

Property $C$: $m$ is prime, and it is guaranteed that $\gcd(n,m)=1$.

Translated by ChatGPT 5