Compressed Formula

You are given a simple, but long formula in a compressed format. A compressed formula is a sequence of $N$ pairs of an integer $r_i$ and a string $s_i$, which consists only of digits ('0'-'9'), '+', '-', and '*'. To restore the original formula from a compressed formula, first we generate strings obtained by repeating $s_i$ $r_i$ times for all $i$, then we concatenate them in order of the sequence.

You can assume that a restored original formula is well-formed. More precisely, a restored formula satisfies the following BNF:

<expression> := <term> | <expression> '+' <term> | <expression> '-' <term>
<term> := <number> | <term> * <number>
<number> := <digit> | <non-zero-digit> <number>
<digit> := '0' | <non-zero-digit>
<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Here, '+' means addition, '-' means subtraction, and '*' means multiplication of integers.

Your task is to write a program computing the answer of a given formula modulo 1,000,000,007, where $x$ modulo $m$ is a non-negative integer $r$ such that there exists an integer $k$ satisfying $x = km + r$ and $0 \leq r < m$; it is guaranteed that such $r$ is uniquely determined for integers $x$ and $m$.

Input

The input consists of a single test case.

$N$
$r_1$ $s_1$
$r_2$ $s_2$
...
$r_N$ $s_N$

The first line contains a single integer $N$ ($1 \leq N \leq 10^4$), which is the length of a sequence of a compressed formula. The following $N$ lines represents pieces of a compressed formula. The $i$-th line consists of an integer $r_i$ ($1 \leq r_i \leq 10^9$) and a string $s_i$ ($1 \leq |s_i| \leq 10$), where $t_i$ is the number of repetition of $s_i$, and $s_i$ is a piece of an original formula. You can assume that an original formula, restored from a given compressed formula by concatenation of repetition of pieces, satisfies the BNF in the problem statement.

Output

Print the answer of a given compressed formula modulo 1,000,000,007.

Sample Input 1

1
5 1

Output for the Sample Input 1

11111

Sample Input 2

2
19 2*
1 2

Output for the Sample Input 2

1048576

Sample Input 3

2
1 1-10
10 01*2+1

Output for the Sample Input 3

999999825

Sample Input 4

4
3 12+45-12
4 12-3*2*1
5 12345678
3 11*23*45

Output for the Sample Input 4

20008570