Problem Statement

A certain teacher (who wishes to remain anonymous) came up with the following problem while proctoring a final exam, with the Setsubun festival going on close by.

To prevent cheating, students may not sit in adjacent seats at the same desk.
For example, at a desk with $3$ chairs, if $2$ students sit there, the only allowed option is to use the chairs at both ends, and if $1$ student sits there, any of the $3$ chairs may be used.
In a certain room, there are $N$ types of desks, and there are $D_k$ desks with $C_k$ chairs.
Here, a desk with $C_k$ chairs has its $C_k$ chairs arranged in a straight line.
Write a program that finds the maximum number of students who can take the exam in this room, modulo ${\rm mod}\ 10^9+7$.

Figure 1. The place where this problem was born (Kyoto University, Room 1-Kyo-01, February 4, 2015)

Input

$N$
$C_1$ $D_1$
$C_2$ $D_2$
$\vdots$
$C_N$ $D_N$

$1 \leq N \leq 100000 = 10^5$
$1 \leq C_k \leq 10^{18}$
$1 \leq D_k \leq 10^{18}$
$C_i \neq C_j$ when $i \neq j$

Output

Output the maximum number of students who can take the exam in this room, modulo ${\rm mod}\ 10^9+7$.

Sample

2
2 5
3 20

45