Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

F. Длинное число
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующую грамматику:

  • <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'

Эта грамматика задаёт число в десятичной системе счисления по следующим правилам:

  • <number> задаёт себя,
  • <number>-<number> (l-r, l ≤ r) задаёт число, полученное как конкатенация всех чисел от l до r, записанных без ведущих нулей. Например, 8-11 задает число 891011,
  • <number>(<expression>) задаёт число, полученное как конкатенация <number> копий числа, задаваемого <expression>,
  • <expression>+<term> задаёт число, полученное как конкатенация чисел, задаваемых <expression> и <term>.

Пример: 2(2-4+1)+2(2(17)) задаёт число 2341234117171717.

Дано выражение, выведите остаток от деления числа, которое оно задаёт, на 109 + 7.

Входные данные

В единственной строке ввода записана непустая строка длины не более 105, соответствующая заданной грамматике. В частности, для термов вида l-r гарантируется l ≤ r.

Выходные данные

В единственной строке выведите остаток от деления числа, задаваемого выражением, на 109 + 7.

Примеры
Входные данные
8-11
Выходные данные
891011
Входные данные
2(2-4+1)+2(2(17))
Выходные данные
100783079
Входные данные
1234-5678
Выходные данные
745428774
Входные данные
1+2+3+4-5+6+7-9
Выходные данные
123456789