It's time for Oliver to do his daily chores. There are ~N~ different types of chores. The ~i^\text{th}~ ~(1 \le i \le N)~ type takes Oliver ~a_i~ minutes to complete and there are ~b_i~ chores of that type. Oliver starts a stopwatch and gets right to work on the chores. Each time he completes a chore, he writes down the time in minutes on the stopwatch, and then immediately starts completing his next chore. Once he has completed all the chores, he calculates his efficiency score by adding up all the times he wrote down. Can you help Oliver minimize his efficiency score?

Input Specification

The first line will contain one integer ~N~ ~(1 \le N \le 10^5)~.

The next ~N~ lines will each contain two integers. The ~i^\text{th}~ ~(1 \le i \le N)~ line will contain ~a_i~ ~(1 \le a_i \le 10^9)~ and ~b_i~ ~(1 \le b_i \le 10^9)~.

Output Specification

Print one integer, the minimum efficiency score possible. Since this number may be very large, output it modulo ~10^9 + 7~.

Sample Input 1

3
2 1
4 3
1 2

Sample Output 1

43

Sample Input 2

1
100 1000000000

Sample Output 2

2100

Sample Input 3

5
6 3
2 4
1 1
10 12
3 4

Sample Output 3

1438