{"raw_statement":[{"iden":"statement","content":"A _simplified arithmetic expression_ (SAE) is an arithmetic expression defined by the following grammar:\n\n*   _<SAE> ::= <Number> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)_\n*   _<Number> ::= <Digit> | <Digit><Number>_\n*   _<Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9_\n\nIn other words it's a correct arithmetic expression that is allowed to contain brackets, numbers (possibly with leading zeros), multiplications and additions. For example expressions \"_(0+01)_\", \"_0_\" and \"_1*(0)_\" are simplified arithmetic expressions, but expressions \"_2-1_\", \"_+1_\" and \"_1+2)_\" are not.\n\nGiven a string _s_1_s_2..._s_|_s_| that represents a SAE; _s__i_ denotes the _i_\\-th character of the string which can be either a digit ('_0_'-'_9_'), a plus sign ('_+_'), a multiplication sign ('_*_'), an opening round bracket '_(_' or a closing round bracket '_)_'.\n\nA part _s__l__s__l_ + 1..._s__r_ of this string is called a _sub-expression_ if and only if it is a SAE.\n\nYou task is to answer _m_ queries, each of which is a pair of integers _l__i_, _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ |_s_|). For each query determine whether the corresponding part of the given string is a sub-expression and in case it's a sub-expression calculate its value modulo 1000000007 (109 + 7). The values should be calculated using standard operator priorities."},{"iden":"input","content":"The first line of the input contains non-empty string _s_ (1 ≤ |_s_| ≤ 4·105) which represents a correct SAE. Each character of the string can be one of the following characters: '_*_', '_+_', '_(_', '_)_' or a digit ('_0_'-'_9_'). The expression might contain extra-huge numbers.\n\nThe second line contains an integer _m_ (1 ≤ _m_ ≤ 4·105) which is the number of queries. Each of the next _m_ lines contains two space-separated integers _l__i_, _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ |_s_|) — the _i_\\-th query."},{"iden":"output","content":"The _i_\\-th number of output should be the answer for the _i_\\-th query. If the _i_\\-th query corresponds to a valid sub-expression output the value of the sub-expression modulo 1000000007 (109 + 7). Otherwise output -1 as an answer for the query. Print numbers on separate lines."},{"iden":"examples","content":"Input\n\n((1+2)*3+101*2)\n6\n8 14\n1 6\n2 10\n11 14\n5 5\n4 5\n\nOutput\n\n205\n-1\n10\n2\n2\n-1\n\nInput\n\n(01)\n1\n1 4\n\nOutput\n\n1"}],"translated_statement":[{"iden":"statement","content":"一个_简化算术表达式_（SAE）是由以下文法定义的算术表达式：\n\n换句话说，它是一个合法的算术表达式，允许包含括号、数字（可能带有前导零）、乘法和加法。例如，表达式 \"_(0+01)_\"、\"_0_\" 和 \"_1*(0)_\" 是简化算术表达式，但表达式 \"_2-1_\"、\"_+1_\" 和 \"_1+2)_\" 不是。\n\n给定一个表示 SAE 的字符串 #cf_span[s1s2...s|s|]；#cf_span[si] 表示字符串的第 #cf_span[i] 个字符，它可以是数字（'_0_'-'_9_'）、加号（'_+_'）、乘号（'*'）、左括号 '_(_' 或右括号 '_)_'。\n\n该字符串的子串 #cf_span[slsl + 1...sr] 被称为一个_子表达式_，当且仅当它是一个 SAE。\n\n你的任务是回答 #cf_span[m] 个查询，每个查询是一对整数 #cf_span[li], #cf_span[ri] #cf_span[(1 ≤ li ≤ ri ≤ |s|)]。对于每个查询，判断给定字符串的对应部分是否为子表达式；如果是子表达式，则计算其值对 #cf_span[1000000007 (109 + 7)] 取模的结果。计算值时应使用标准运算符优先级。\n\n输入的第一行包含一个非空字符串 #cf_span[s] #cf_span[(1 ≤ |s| ≤ 4·105)]，表示一个合法的 SAE。字符串中的每个字符可以是以下字符之一：'_*_', '_+_', '_(_', '_)_' 或数字（'_0_'-'_9_'）。表达式可能包含超大数字。\n\n第二行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 4·105)]，表示查询的数量。接下来的 #cf_span[m] 行每行包含两个用空格分隔的整数 #cf_span[li], #cf_span[ri] #cf_span[(1 ≤ li ≤ ri ≤ |s|)] —— 第 #cf_span[i] 个查询。\n\n输出的第 #cf_span[i] 个数应为第 #cf_span[i] 个查询的答案。如果第 #cf_span[i] 个查询对应一个有效的子表达式，则输出该子表达式的值对 #cf_span[1000000007 (109 + 7)] 取模的结果；否则输出 -1。每行输出一个数字。"},{"iden":"input","content":"输入的第一行包含一个非空字符串 #cf_span[s] #cf_span[(1 ≤ |s| ≤ 4·105)]，表示一个合法的 SAE。字符串中的每个字符可以是以下字符之一：'_*_', '_+_', '_(_', '_)_' 或数字（'_0_'-'_9_'）。表达式可能包含超大数字。第二行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 4·105)]，表示查询的数量。接下来的 #cf_span[m] 行每行包含两个用空格分隔的整数 #cf_span[li], #cf_span[ri] #cf_span[(1 ≤ li ≤ ri ≤ |s|)] —— 第 #cf_span[i] 个查询。"},{"iden":"output","content":"输出的第 #cf_span[i] 个数应为第 #cf_span[i] 个查询的答案。如果第 #cf_span[i] 个查询对应一个有效的子表达式，则输出该子表达式的值对 #cf_span[1000000007 (109 + 7)] 取模的结果；否则输出 -1。每行输出一个数字。"},{"iden":"examples","content":"输入：\n((1+2)*3+101*2)\n6\n8 14\n1 6\n2 10\n11 14\n5 5\n4 5\n输出：\n20\n5\n-1\n102\n2\n-1\n\n输入：\n(01)\n1\n1 4\n输出：\n1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\{ \\text{digits}, +, *, (, ) \\}^* $ be a string representing a valid Simplified Arithmetic Expression (SAE).  \nLet $ \\mathcal{L} $ be the language of SAEs defined by the grammar:  \n- $ \\text{expr} \\to \\text{term} \\; (\\texttt{+} \\; \\text{term})* $  \n- $ \\text{term} \\to \\text{factor} \\; (\\texttt{*} \\; \\text{factor})* $  \n- $ \\text{factor} \\to \\text{number} \\; | \\; \\texttt{(} \\; \\text{expr} \\; \\texttt{)} $  \n- $ \\text{number} \\to \\text{digit}^+ $  \n- $ \\text{digit} \\in \\{ \\texttt{0}, \\dots, \\texttt{9} \\} $  \n\nA substring $ s[l:r] $ is a *sub-expression* if and only if $ s[l:r] \\in \\mathcal{L} $.  \n\n**Constraints**  \n1. $ 1 \\le |s| \\le 4 \\cdot 10^5 $  \n2. $ 1 \\le m \\le 4 \\cdot 10^5 $  \n3. For each query $ (l_i, r_i) $: $ 1 \\le l_i \\le r_i \\le |s| $  \n\n**Objective**  \nFor each query $ (l_i, r_i) $:  \n- If $ s[l_i:r_i] \\in \\mathcal{L} $, compute $ v_i = \\text{eval}(s[l_i:r_i]) \\mod 1000000007 $  \n- Otherwise, output $ -1 $  \n\nOutput $ m $ lines, each containing $ v_i $ or $ -1 $.","simple_statement":null,"has_page_source":false}