#3114. Uva12546 Lcm Pair Sum

内存限制:128 MiB 时间限制:1 Sec

题目描述

给定一个数N,求所有满足最小公倍数为N的a,b的和对1000000007取模.

例如当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 1000000007。

样例

样例输入


			
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<=500,m<=15,每个质因数是2-1000内的质数,次数大于等于1小于等于50