[LMXOI Round 1] Dreamer

定义积性函数 $f(n)=(\mu \ast\operatorname{Id_2})(n)$。 给定 $n,k$，你需要求出 $$\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$ 表示莫比乌斯函数。 关于 $f$，$f(n)=\displaystyle \sum_{d\mid n}\mu(d)\left(\dfrac{n}{d}\right)^2$。 ## Input 本题有多组数据，第一行输入一个正整数 $T$，表示数据组数。 考虑到 $n$ 很大，所以我们会给出 $n$ 的标准质因子分解 $n=\displaystyle \prod_{i=1}^t p_i^{\alpha_i}$。 对于每一组询问，我们首先给出两个整数 $k,m$。 第二行给出 $t$，下面 $t$ 行每行两个整数表示 $p_i,\alpha_i$。 （保证 $p_i\ge p_{i-1},i\ge 2$，$\alpha_i\ge 1$）。 ## Output 对于每个询问，输出一行表示答案 $\mod m$ 的值。 [samples] ## Background [加强版链接](https://www.luogu.com.cn/problem/U402756)。 这是一道数学题，可是 LMX 给 HQZ 出的。 ## Note 对于 $100\%$ 的数据，有 $T \le 20,n\le 10^{24},1\le k\le 10^6,m\le 1.14\times 10^9$。 | 测试点编号 | $n$ | $k$ | $T$ | 特殊性质 | | :--------: | :-----------: | :--------: | :------: | :------: | | $1$ | $\le 80$ | $\le 4$ | $\le 5$ | $N$ | | $2$ | $\le 10^6$ | $\le 10$ | $\le 5$ | $N$ | | $3$ | $\le 10^{12}$ | $\le 20$ | $\le 20$ | $N$ | | $4$ | $\le 10^{18}$ | $\le 1$ | $\le 20$ | $N$ | | $5$ | $\le 10^{18}$ | $\le 10^3$ | $\le 20$ | $N$ | | $6$ | $\le 10^{18}$ | $\le 10^5$ | $\le 20$ | $A$ | | $7$ | $\le 10^{18}$ | $\le 10^6$ | $\le 20$ | $B$ | | $8$ | $\le 10^{24}$ | $\le 10^6$ | $\le 20$ | $B$ | | $9$ | $\le 10^{24}$ | $\le 10^6$ | $\le 20$ | $C$ | | $10\sim20$ | $\le 10^{24}$ | $\le 10^6$ | $\le 20$ | $N$ | 性质 $A$：保证 $t\le 10$。 性质 $B$：保证 $n$ 的质因子分解 $\displaystyle\prod_{i=1}^t p_i^{\alpha_i}$ 中 $\alpha_i=1$。 性质 $C$：$m$ 是素数，且保证 $\gcd(n,m)=1$。