Eric Barkman, the founder of the startup Aviato, has decided to leave the company and retreat to the mountains of Tibet to find inner peace. Before he goes, he must do a "baton touch" and transfer all of his critical knowledge to his successor, Jin.

Eric holds ~n~ pieces of knowledge, numbered ~1~ through to ~n~. Each piece has:

• An initial complexity ~c_i~, the time it would take to transfer the knowledge immediately;
• A growth rate ~g_i~, where every hour that passes before Eric begins transferring piece ~i~ increases the complexity by ~g_i~.

Only one piece of knowledge can be transferred at a time, starting from ~t=0~. If Eric begins transferring piece ~i~ at time ~t~, the transfer takes exactly ~c_i + g_i \times t~ hours, after which ~t~ advances by that amount.

Jin is a fast learner, but he's also busy. He charges a frustration fee equal to the transfer duration of each piece (i.e. how long he has to sit and listen). Eric wants to minimise the total frustration fee across all ~n~ pieces.

Input

The first line contains an integer ~n~ ~(1 \leq n \leq 10^5)~, the pieces of knowledge to transfer.

The next ~n~ lines contain integers ~c_i~ ~(1 \leq c_i \leq 10^4)~ and ~g_i~ ~(1 \leq g_i \leq 10^4)~, which represent the initial complexity and growth rate of the ~i~th piece of knowledge.

Output

Print a single integer, the minimum total frustration fee. The answer may be very large, so return it modulo ~10^9 + 7~.

Example

Input 1

2
5 1
1 4

Output 1

7

Input 2

4
5 2
3 5
8 1
2 4

Output 2

108