Sum of Scores of Built Arrays

For each position i, choose any prime from the closed interval [low[i],high[i]] to form an array. The score of an array is the product of all its elements. Find the sum of scores over all distinct valid arrays, modulo 10⁹+7. Each interval is guaranteed to contain at least one prime. The ranges and modulo rule truncated during import have been restored from the original statement.

This site has made the standard input and output explicit.

输入格式

The first line contains n, followed by n lines of low high; 1≤n≤100000, 1≤low≤high≤1000000, and each interval contains at least one prime.

输出格式

Output one integer, the answer.

样例 1

输入：

2
1 3
3 5

输出：

40

样例 2

输入：

3
2 2
2 2
2 2

输出：

8

样例 3

输入：

3
1 4
2 5
3 30

输出：

6350

样例说明

Example 1: (2+3)×(3+5)=40. Example 2: all three positions can only choose 2, giving a product of 8; the original second example [1,1] contains no prime, violating the guarantee, so it was changed to [2,2]. Example 3: the three prime sums are 5, 10 and 127, with product 6350; the original output 30 counted only one combination.