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$.

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.

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

1 5 1

11111

2 19 2* 1 2

1048576

2 1 1-10 10 01*2+1

999999825

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

20008570

Source: JAG Practice Contest for ACM-ICPC Asia Regional 2016
, Japan, 2016-9-4

http://jag-icpc.org/

http://jag2016autumn.contest.atcoder.jp/

http://jag-icpc.org/

http://jag2016autumn.contest.atcoder.jp/