题目描述

Dirichlet卷积

定义:
定义两个数论函数 $f$ 和 $g$ 的Dirichlet卷积为 $(f * g)(n) = \sum_{d|n} f(d)g(\frac{n}{d})$

性质:
Dirichlet卷积满足以下运算规律:
交换律: $f * g = g * f$
结合律: $(f * g) * h = f * (g * h)$
分配律: $f * (g + h) = f * g + f * h$

现在令 $f(x) = \varphi(x),g(x) = x$ ,
其中 $\varphi(x)$ 为欧拉函数, 代表小于或等于 $x$ 的正整数中与 $x$ 互质的数的数目。
其中$\varphi(1) = 1$

求 $(f * g)(n) \mod (10^9 + 7) $ 的值。


输入格式

第一行,一个 $t(1\leq t \leq 10)$ ,代表输入数据的组数

每一组输入数据:
第一行,一个正整数 $m(1 \leq m \leq 10^5)$ ,代表正整数 $n$ 的质因子的种类。
接下来 $m$ 行,每行包含两个正整数 $p_i, q_i(2 \le p_i \le 3 * 10^8,1 \le q_i \le 10^8)$ ,代表 $p_i^{q_i}$ 是 $n$ 的因数。

即 $n = \prod_{i = 1}^{m} p_i^{q_i}$。 输入保证所有的 $p_i$ 均是质数,且两两互不相同。


输出格式

对每一组输入数据,输出 $(f*g)(n) \mod (10^9 + 7)$ 的值。


样例数据

输入

2
2
2 1
3 1
2
2 2 
3 2

输出

15
168

备注

样例输入1中, $n=2^1\cdot 3^1=6$ ,$6$ 有 $4$ 个因数,分别是 $1,2,3,6$ ,故所求为 $(f*g)(n)=f(1)g(6)+f(2)g(3)+f(3)g(2)+f(6)g(1)=6+3+4+2=15$ 。


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务