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, for a desk with $3$ chairs, if $2$ students sit there, the only allowed way 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.
It is not known how many people will take the exam, but write a program that computes the number of possible patterns of arrangements of used chairs, ${\rm mod}\ 10^9+7$.

Figure 1. Apparently the Setsubun festival continues the day after the exam day (2/3) as well... (in front of Yoshida Shrine, February 4, 2015)

Input

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

$1 \leq N \leq 30000 = 3 \times 10^4$
$1 \leq C_k \leq 10^{18}$
$1 \leq D_k \leq 10^{200}$
$C_i \neq C_j$ when $i \neq j$

Output

Output the number of patterns of used chairs, ${\rm mod}\ 10^9+7$.

Sample

1
3 1

5

2
1 2
3 1

20

3
10 10
20 20
30 30

500979274