简化算术表达式 (SAE) 是由以下语法定义的算术表达式:
- <SAE> ::= <数字> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)
- <数字> ::= <数字> | <数字><数字>
- <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
换句话说,它是一个正确的算术表达式,允许包含括号、数字(可能带有前导零)、乘法和加法。例如,表达式“(0+01)”、“0”和“1*(0)”是简化的算术表达式,但表达式“2-1”、“+1”和“1+2)”则不是。
给定一个字符串 s1s2...s|s|代表 SAE; si 表示字符串的第 i 个字符,可以是数字 ('0'-'9')、加号 ('+')、乘号 ('*')、左圆括号 '(' 或右圆括号 ')'。
当且仅当它是 SAE 时,该字符串的一部分 slsl + 1...sr 称为子表达式。
你的任务是回答 m 个查询,每个查询都是一对整数 li, ri (1 ≤ li ≤ ri ≤ |s|)。对于每个查询,确定给定字符串的相应部分是否是子表达式,如果是子表达式,则计算其值模 1000000007 (109 + 7)。应使用标准操作员优先级来计算这些值。
输入
输入的第一行包含非空字符串 s (1 ≤ |s| ≤ 4·105),它表示正确的 SAE。字符串的每个字符可以是以下字符之一:'*'、'+'、'('、')' 或数字 ('0'-'9')。该表达式可能包含超大数字。
第二行包含一个整数m (1 ≤ m ≤ 4·105),它是查询的数量。接下来的 m 行中的每一行都包含两个以空格分隔的整数 li, ri (1 ≤ li ≤ ri ≤ |s|) — 第 i 个查询。
输出
第 i 个输出数应该是第 i 个查询的答案。如果第 i 个查询对应于有效的子表达式,则输出子表达式的值模 1000000007 (109 + 7)。否则输出 -1 作为查询的答案。在单独的行上打印数字。
示例
输入 #1
((1+2)*3+101*2) 6 8 14 1 6 2 10 11 14 5 5 4 5
输出 #1
205 -1 10 2 2 -1
输入 #2
(01) 1 1 4
输出 #2
1