Least common multiple

Problem Description
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).

Input
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).

Output
For each tests:

A single integer, the value of the sum.

Sample Input
2
0 1
1 0
3
1 2
2 1
1 2

Sample Output
11
174