Long number

题意翻译

考虑下面的算法（设 A，B 为自然数）： - A ：表示 A 本身。 - A-B ：不间断地输出 A 到 B 之间的数（ $A\le B$ ），例如 8-11，表示 891011。 - A(B)：把数字 B 重复 A 遍。 - A+B：连接数字 A 和 B。 举个例子，2(2-4+1)+2(2(17)) 表示的数是 2341234117171717。 现在请你输出在如上规则下的数对 $10^9+7$ 取余的结果（输入的长度不超过 $10^5$）。

题目描述

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

输入输出格式

输入格式

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.

输出格式

Print single integer — the number described by the expression modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

8-11

输出样例 #1

891011

输入样例 #2

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

输出样例 #2

100783079

输入样例 #3

1234-5678

输出样例 #3

745428774

输入样例 #4

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

输出样例 #4

123456789