Least common multiple

Problem Description

bobo has an integer set S={x₁,x₂,…,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⁹+7).

 

Input

The input consists of several tests. For each tests:

The first line contains n (1≤n≤10⁵). Each of the following n lines contain 2 integers a_i,b_i (0≤a_i,b_i≤10⁹).

 

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