Arithmetic of Bomb II

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

它最近在学习小学算术，沉迷于计算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），再来计算这个表达式的结果。

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

每组数据包含一个Bomb Expression。

●1≤T≤50

●1≤length(Bomb Statement)≤10

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

●1≤length(Bomb Expression)≤300 000

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

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

2
60
111
3
43
343

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