Least common multiple
TimeLimit:3000MS MemoryLimit:131072KB
64-bit integer IO format:%I64d
Problem Description
bobo has an integer set S={x
1,x
2,…,x
n}, where x
i=2
ai * 3
bi.
For each non-empty subsets of S, bobo added the LCM (least common multiple) of the subset up. Find the sum of LCM modulo (10
9+7).
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤10
5). Each of the following n lines contain 2 integers a
i,b
i (0≤a
i,b
i≤10
9).
Output
For each tests:
A single integer, the value of the sum.