← 返回题目列表

Codeforces · 756/F

F. 长号码

中文机器翻译题面 查看原题

考虑以下语法:

- <表达式> ::= <术语> | <表达式> '+' <术语>
- <术语> ::= <数字> | <数字> '-' <数字> | <数字> '(' <表达式> ')'
- <数字> ::= <位置数字> | <数字> <数字>
- <数字> ::= '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