{"raw_statement":[{"iden":"statement","content":"Consider the following grammar:\n\n*   _<expression> ::= <term> | <expression> '+' <term>_\n*   _<term> ::= <number> | <number> '-' <number> | <number> '(' <expression> ')'_\n*   _<number> ::= <pos_digit> | <number> <digit>_\n*   _<digit> ::= '0' | <pos_digit>_\n*   _<pos_digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'_\n\nThis grammar describes a number in decimal system using the following rules:\n\n*   _<number>_ describes itself,\n*   _<number>-<number>_ (_l-r_, _l_ ≤ _r_) describes integer which is concatenation of all integers from _l_ to _r_, written without leading zeros. For example, _8-11_ describes _891011_,\n*   _<number>(<expression>)_ describes integer which is concatenation of <number> copies of integer described by _<expression>_,\n*   _<expression>+<term>_ describes integer which is concatenation of integers described by _<expression>_ and _<term>_.\n\nFor example, _2(2-4+1)+2(2(17))_ describes the integer _2341234117171717_.\n\nYou are given an expression in the given grammar. Print the integer described by it modulo 109 + 7."},{"iden":"input","content":"The only line contains a non-empty string at most 105 characters long which is valid according to the given grammar. In particular, it means that in terms _l-r_ _l_ ≤ _r_ holds."},{"iden":"output","content":"Print single integer — the number described by the expression modulo 109 + 7."},{"iden":"examples","content":"Input\n\n8-11\n\nOutput\n\n891011\n\nInput\n\n2(2-4+1)+2(2(17))\n\nOutput\n\n100783079\n\nInput\n\n1234-5678\n\nOutput\n\n745428774\n\nInput\n\n1+2+3+4-5+6+7-9\n\nOutput\n\n123456789"}],"translated_statement":[{"iden":"statement","content":"考虑以下文法：\n\n该文法使用以下规则描述十进制系统中的数字：\n\n例如，_2(2-4+1)+2(2(17))_ 描述整数 _2341234117171717_。\n\n给定一个符合该文法的表达式，请输出其描述的整数对 #cf_span[109 + 7] 取模的结果。\n\n输入仅有一行，包含一个非空字符串，长度不超过 #cf_span[105]，且符合上述文法。特别地，这意味着在形如 _l-r_ 的项中，#cf_span[l ≤ r] 成立。\n\n请输出一个整数——该表达式所描述的数对 #cf_span[109 + 7] 取模的结果。\n\n"},{"iden":"input","content":"输入仅有一行，包含一个非空字符串，长度不超过 #cf_span[105]，且符合上述文法。特别地，这意味着在形如 _l-r_ 的项中，#cf_span[l ≤ r] 成立。"},{"iden":"output","content":"请输出一个整数——该表达式所描述的数对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入\n8-11\n输出\n891011\n\n输入\n2(2-4+1)+2(2(17))\n输出\n100783079\n\n输入\n1234-5678\n输出\n745428774\n\n输入\n1+2+3+4-5+6+7-9\n输出\n123456789"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G $ be a grammar over alphabet $ \\Sigma = \\{0,1,\\dots,9, +, -, (, )\\} $, with recursive production rules:  \n- A *term* is a digit $ d \\in \\{0,1,\\dots,9\\} $, or a compound expression of the form $ l - r $ or $ n(E) $, where:  \n  - $ l, r $ are terms with $ l \\leq r $ (inclusive range),  \n  - $ n \\in \\mathbb{Z}_{\\geq 1} $ is a positive integer (multiplier),  \n  - $ E $ is a term.  \n\nThe semantics of a term $ T $ is a string $ s(T) \\in \\{0,1,\\dots,9\\}^* $, defined recursively:  \n- If $ T = d $, then $ s(T) = d $ (as a string).  \n- If $ T = l - r $, then $ s(T) = \\bigcup_{k=l}^{r} s(k) $, i.e., concatenation of strings $ s(l), s(l+1), \\dots, s(r) $.  \n- If $ T = n(E) $, then $ s(T) = s(E)^n $, i.e., $ s(E) $ repeated $ n $ times.  \n\nLet $ N(T) $ be the integer value of the decimal string $ s(T) $, interpreted in base 10.\n\n**Constraints**  \n- Input is a single string $ T $ of length $ \\leq 10^5 $, valid under grammar $ G $.  \n- All numeric literals in ranges $ l, r $ satisfy $ l \\leq r $.  \n\n**Objective**  \nCompute $ N(T) \\mod (10^9 + 7) $.","simple_statement":null,"has_page_source":false}