D. Арифметическое выражение
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Определим арифметическое выражение (АВ) следующим образом.

  • Каждое неотрицательное целое число является АВ. Целые числа могут иметь лидирующие нули (например, 0000 и 0010 считаются допустимыми целыми числами).
  • Если X и Y являются АВ, то «(X) + (Y)», «(X) - (Y)», «(X) * (Y)», и «(X) / (Y)» (без кавычек) тоже являются АВ.
  • Если X является АВ, то « - (X)» и « + (X)» (без кавычек) тоже являются АВ.

    Дана строка, состоящая из цифр («0» - «9») и символов «-», «+», «*», и «/». Ваша задача — посчитать количество арифметических выражений, таких, что после удаления из него всех скобок (символов «(» и «)»), это выражение становится эквивалентным данной строке. Так как ответ может быть очень большим, выведите его по модулю 1000003 (106 + 3).

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

Первая строка — непустая строка из цифр («0» - «9») и символов «-», «+», «*», и/или «/». Длина строки не превосходит 2000 символов. Строка не содержит пробелов.

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

Выведите одно целое число — количество различных арифметических выражений, которые после удаления из них скобок становятся посимвольно равными данной строке, по модулю 1000003 (106 + 3).

Примеры
Входные данные
1+2*3
Выходные данные
2
Входные данные
03+-30+40
Выходные данные
3
Входные данные
5//4
Выходные данные
0
Входные данные
5/0
Выходные данные
1
Входные данные
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
Выходные данные
100728
Примечание

В первом примере возможны два арифметических выражения:

((1) + (2)) * (3)
(1) + ((2) * (3))

Во втором примере возможны три арифметических выражения:

(03) + (( - (30)) + (40))
(03) + ( - ((30) + (40)))
((03) + ( - (30))) + (40)