F. Long number

Codeforces

IDCF756F

Time2000ms

Memory512MB

Difficulty—

expression parsingmathnumber theory

Consider the following grammar: * _<expression> ::= <term> | <expression> '+' <term>_ * _<term> ::= <number> | <number> '-' <number> | <number> '(' <expression> ')'_ * _<number> ::= <pos_digit> | <number> <digit>_ * _<digit> ::= '0' | <pos_digit>_ * _<pos_digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'_ This grammar describes a number in decimal system using the following rules: * _<number>_ describes itself, * _<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_, * _<number>(<expression>)_ describes integer which is concatenation of <number> copies of integer described by _<expression>_, * _<expression>+<term>_ describes integer which is concatenation of integers described by _<expression>_ and _<term>_. For example, _2(2-4+1)+2(2(17))_ describes the integer _2341234117171717_. You are given an expression in the given grammar. Print the integer described by it modulo 109 + 7. ## Input 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. ## Output Print single integer — the number described by the expression modulo 109 + 7. [samples]

Samples

Input #1

8-11

Output #1

Input #2

2(2-4+1)+2(2(17))

Output #2

100783079

Input #3

1234-5678

Output #3

745428774

Input #4

1+2+3+4-5+6+7-9

Output #4

123456789

API Response (JSON)

{
  "problem": {
    "name": "F. Long number",
    "description": {
      "content": "Consider the following grammar: *   _<expression> ::= <term> | <expression> '+' <term>_ *   _<term> ::= <number> | <number> '-' <number> | <number> '(' <expression> ')'_ *   _<number> ::= <pos_digit>",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF756F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the following grammar:\n\n*   _<expression> ::= <term> | <expression> '+' <term>_\n*   _<term> ::= <number> | <number> '-' <number> | <number> '(' <expression> ')'_\n*   _<number> ::= <pos_digit>...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments