Long number

Consider the following grammar:

• ::= | '+'
• ::= | '-' | '(' ')'
• ::= <pos_digit> |
• ::= '0' | <pos_digit>
• <pos_digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

This grammar describes a number in decimal system using the following rules:

• describes itself,
• - (l-r, l ≤ r) describes integer which is concatenation of all integers from l to r, written without leading zeros. For example, 8-11 describes 891011,
• () describes integer which is concatenation of copies of integer described by ,
• + describes integer which is concatenation of integers described by and .

For example, 2(2-4+1)+2(2(17)) describes the integer 2341234117171717.

You are given an expression in the given grammar. Print the integer described by it modulo 109 + 7.

Input

The only line contains a non-empty string at most 105 characters long which is valid according to the given grammar. In particular, it means that in terms l-r l ≤ r holds.

Output

Print single integer — the number described by the expression modulo 109 + 7.

Examples

Input

8-11

Output

891011

Input

2(2-4+1)+2(2(17))

Output

100783079

Input

1234-5678

Output

745428774

Input

1+2+3+4-5+6+7-9

Output

123456789

inputFormat

Input

The only line contains a non-empty string at most 105 characters long which is valid according to the given grammar. In particular, it means that in terms l-r l ≤ r holds.

outputFormat

Output

Print single integer — the number described by the expression modulo 109 + 7.

Examples

Input

8-11

Output

891011

Input

2(2-4+1)+2(2(17))

Output

100783079

Input

1234-5678

Output

745428774

Input

1+2+3+4-5+6+7-9

Output

123456789

样例

8-11

891011

</p>