AOJ 4290 - Least common multiple

Least common multiple

Time Limit: 3000ms

Memory Limit: 131072KB

This problem will be judged on HDU. Original ID: 4913
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

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

Sample Output

11
174

Source

2014 Multi-University Training Contest 5