考虑以下语法:
- <表达式> ::= <术语> | <表达式> '+' <术语>
- <术语> ::= <数字> | <数字> '-' <数字> | <数字> '(' <表达式> ')'
- <数字> ::= <位置数字> | <数字> <数字>
- <数字> ::= '0' | <位置数字>
- <pos_digit> ::= '1' | '2'| '3'| '4'| '5'| '6'| '7'| '8'| ‘9’
该语法使用以下规则描述十进制系统中的数字:
- <数字> 描述其自身,
- <number>-<number> (l-r, l ≤ r) 描述整数,它是从 l 到 r 的所有整数的串联,不带前导零。例如,8-11描述了891011,
- <number>(<表达式>) 描述整数,它是由 <表达式> 描述的整数的 <number> 个副本串联而成,
- <表达式>+<术语>描述由<表达式>和<术语>描述的整数串联而成的整数。
例如,2(2-4+1)+2(2(17)) 描述整数 2341234117171717。
给你一个给定语法中的表达式。打印它描述的整数模 109 + 7。
输入
唯一的一行包含一个最多 105 个字符长的非空字符串,根据给定的语法该字符串是有效的。特别是,这意味着在 l-r 项中 l ≤ r 成立。
输出
打印单个整数 — 由表达式模 109 + 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