2450: Least common multiple
内存限制:128 MB
时间限制:10.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
bobo has an integer set S={x1,x2,…,xn}, where xi=2ai * 3bi.
For each non-empty subsets of S, bobo added the LCM (least common multiple) of the subset up. Find the sum of LCM modulo (109+7).
输入
The input consists of several tests. For each tests:
The first line contains n (1≤n≤105). Each of the following n lines contain 2 integers ai,bi (0≤ai,bi≤109).
输出
For each tests:
A single integer, the value of the sum.
样例输入 复制
2
0 1
1 0
3
1 2
2 1
1 2
样例输出 复制
11
174