Определим арифметическое выражение (АВ) следующим образом.
- Каждое неотрицательное целое число является АВ. Целые числа могут иметь лидирующие нули (например, 0000 и 0010 считаются допустимыми целыми числами).
- Если X и Y являются АВ, то «(X) + (Y)», «(X) - (Y)», «(X) * (Y)», и «(X) / (Y)» (без кавычек) тоже являются АВ.
- Если X является АВ, то « - (X)» и « + (X)» (без кавычек) тоже являются АВ.
Дана строка, состоящая из цифр («0» - «9») и символов «-», «+», «*», и «/». Ваша задача — посчитать количество арифметических выражений, таких, что после удаления из него всех скобок (символов «(» и «)»), это выражение становится эквивалентным данной строке. Так как ответ может быть очень большим, выведите его по модулю 1000003 (106 + 3).
Выходные данные
Выведите одно целое число — количество различных арифметических выражений, которые после удаления из них скобок становятся посимвольно равными данной строке, по модулю 1000003 (106 + 3).
Примечание
В первом примере возможны два арифметических выражения:
((1) + (2)) * (3)
(1) + ((2) * (3))
Во втором примере возможны три арифметических выражения:
(03) + (( - (30)) + (40))
(03) + ( - ((30) + (40)))
((03) + ( - (30))) + (40)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1+2*3
|
2
|
|
2
|
03+-30+40
|
3
|
|
3
|
5//4
|
0
|
|
4
|
5/0
|
1
|
|
5
|
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
|
100728
|