Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Long number

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputConsider the following grammar:

- <expression> ::= <term> | <expression> '+' <term>
- <term> ::= <number> | <number> '-' <number> | <number> '(' <expression> ')'
- <number> ::= <pos_digit> | <number> <digit>
- <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:

- <number> describes itself,
- <number>-<number> (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, - <number>(<expression>) describes integer which is concatenation of <number> copies of integer described by <expression>,
- <expression>+<term> describes integer which is concatenation of integers described by <expression> and <term>.

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 10^{9} + 7.

Input

The only line contains a non-empty string at most 10^{5} 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 10^{9} + 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:38:45 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|