Arithmetic of Bomb II

Time Limit: 30000/15000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

众所周知,度度熊非常喜欢数字。

它最近在学习小学算术,沉迷于计算A+B中不能自拔。

但是这回的算术题可并不简单,由于含有表示bomb的#号,度度熊称之为 Arithmetic of Bomb。



Arithmetic of Bomb的目的与普通算术一样,就是计算一些Bomb Expression的结果。比如,”1-2+3”的结果为2。然而,bomb,也就是#号,会展开一些普通表达式,这会导致需要计算的式子超出了度度熊所能理解的范畴。比如”(1-2+3)#(3)”表示”1-2+3”出现了3次,将会被展开为”1-2+31-2+31-2+3”。

为了方便理解,下面给出了Bomb Expression的BNF表示。

```
<bomb expression> := <bomb term> | <bomb expression> <bomb term>
<bomb term> := <bomb statement> | '(' <bomb statement> ')' '#' '(' <number> ')'
<bomb statement> := <bomb element> | <bomb statement> <bomb element>
<bomb element> := <digit> | '+' | '-' | '*'
<normal expression> := <norm term> | <normal expression> '+' <norm term> | <normal expression> '-' <norm term>
<norm term> := <number> | <norm term> '*' <number>
<number> := <digit> | <non-zero-digit> <number>
<digit> := '0' | <non-zero-digit>
<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

```


请先将Bomb Expression中所有的#号展开,使其成为Normal Expression(题目的输入保证展开后是一个合法的Normal Expression),再来计算这个表达式的结果。

Input

第一行为T,表示输入数据组数。

每组数据包含一个Bomb Expression。

●1≤T≤50

●1≤length(Bomb Statement)≤10

●1≤length(Number in Bomb term)≤10

●1≤length(Bomb Expression)≤300 000

Output

对每组数据输出表达式的结果,结果对 1 000 000 007 取模。

Sample Input

6 1-2+3 (1-2+3)#(3) (1)#(3) (1+)#(2)1 (2*3+1)#(2) (2)#(2)1+1(2)#(2)

Sample Output

2 60 111 3 43 343

Hint

Source

2017百度之星程序设计大赛 - 复赛

提交代码