题目描述

给定一个数 $n$，求所有满足最小公倍数为 $n$ 的 $a ,b$ 的和。

例如当 $n=6$ 时，有如下对数 $(1,6),(2,6),(2,3),(3,6),(6,6)$，其和为 $(1+6)+(2+6)+(2+3)+(3+6)+(6+6)=7+8+5+9+12=41$。 现在给你 $n$ 的分解质因数式，请你求出相应的值。

输入格式

多组测试数据。第一行 $T$ 表示数据组数。 每组数据第一行为 $m$，表示有 $m$ 的质因子。 下面 $m$ 行，每行两个数，第一行为这个质因子，第二行为这个质因子在 $n$ 中出现的次数。

输出格式

$T$ 行，每行一个整数表示 $f(n)$ 的值。因为答案可能很大，所以只需输出答案 $\mod 10^9+7$。

3
2
2 1
3 1
2
2 2
3 1
1
5 1

Case 1: 41
Case 2: 117
Case 3: 16

数据规模与约定

对于 $100\%$ 的数据，$T\le 500$，$m \le 15$，每个质因数是 $2\sim 10^3$ 内的质数,次数大于等于 $1$ 小于等于 $50$。