跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0956. Long number

  • ID: 962
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 表达式解析
  • 数学
  • 数论
  • 字符串
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Long number

题目描述

F. Long number
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Examples
Input
8-11
Output
891011
Input
2(2-4+1)+2(2(17))
Output
100783079
Input
1234-5678
Output
745428774
Input
1+2+3+4-5+6+7-9
Output
123456789


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 396 题。保留原作者与原赛事署名。