New King's Game

Problem Description

It is the National Day of country $\mathrm{H}$ again, and the king has invited $n$ ministers to play a prize game. After being criticized by the ministers for being stingy at the last National Day, the king decides to be more generous this year: he changes the rules of the game and no longer participates in it, to avoid being questioned by the ministers. First, he asks each minister to write down a positive integer on his left hand and right hand. Then the $n$ ministers line up. After lining up, every minister receives some gold coins from the king's reward; the number of gold coins each minister receives equals the product of the numbers on the left hands of all ministers behind him, multiplied by the number on his own right hand. The king wants the total number of gold coins received by all ministers to be as large as possible, so he would like you to rearrange the order of the line.

In short, given $n$ pairs of numbers $a_i, b_i$, find a permutation order that maximizes $b_1 \times a_2 \cdot a_3 \cdot \dots \cdot a_n + b_2 \times a_3 \cdot a_4 \cdot \dots \cdot a_n + \dots + b_n$, and output the maximum value. Since the answer may be very large, take it modulo $1000000007$.

Input Format

The first line contains an integer $n$.

Lines $2$ to $n+1$ each contain two integers $a_i, b_i$.

Output Format

Output one line: the maximum value of $b_1 \times a_2 \cdot a_3 \cdot \dots \cdot a_n + b_2 \times a_3 \cdot a_4 \cdot \dots \cdot a_n + \dots + b_n$ modulo $1000000007$.

Sample Input

2
1 2
3 4

Sample Output

10

Sample Explanation

There are only two cases:

1 2
3 4

$(2 \times 3) + 4 = 10$

3 4
1 2

$(4 \times 1) + 2 = 6$

So the answer is $10$.

Constraints

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le a_i, b_i \le 2^{30}$.