CF115D.Unambiguous Arithmetic Expression

Let's define an unambiguous arithmetic expression (UAE) as follows.

• All non-negative integers are UAE's. Integers may have leading zeroes (for example, 0000 and 0010 are considered valid integers).

• If X and Y are two UAE's, then "(X) + (Y)", "(X) - (Y)", "(X) * (Y)", and "(X) / (Y)" (all without the double quotes) are UAE's.

• If X is an UAE, then " - (X)" and " + (X)" (both without the double quotes) are UAE's.

  You are given a string consisting only of digits ("0" - "9") and characters "-", "+", "*", and "/". Your task is to compute the number of different possible unambiguous arithmetic expressions such that if all brackets (characters "(" and ")") of that unambiguous arithmetic expression are removed, it becomes the input string. Since the answer may be very large, print it modulo 1000003 (106 + 3).

我们定义一个**无歧义算术表达式（UAE）**如下：

• 所有非负整数均为 UAE。整数可以包含前导零（例如，0000 和 0010 被视为合法的整数）。
• 若 $X$ 和 $Y$ 均为 UAE，则 "($X$) + ($Y$)"、"($X$) - ($Y$)"、"($X$) * ($Y$)" 和 "($X$) / ($Y$)"（均不含双引号）均为 UAE。
• 若 $X$ 是 UAE，则 " - ($X$)" 和 " + ($X$)"（均不含双引号）均为 UAE。

给定一个仅由数字字符（'0'–'9'）以及字符 '-'、'+'、'*' 和 '/' 组成的字符串。你的任务是计算：有多少种不同的可能的无歧义算术表达式，使得将该表达式中所有括号（即字符 '(' 和 ')'）全部移除后，恰好得到输入字符串。由于答案可能非常大，请输出其对 $1000003$（即 $10^6 + 3$）取模的结果。

The first line is a non-empty string consisting of digits ('0'-'9') and characters '-', '+', '*', and/or '/'. Its length will not exceed 2000. The line doesn't contain any spaces.

第一行是一个非空字符串，由数字（'0'–'9'）以及字符 '-'、'+'、'*' 和/或 '/' 组成。该行长度不超过 2000，且不包含任何空格。

Print a single integer representing the number of different unambiguous arithmetic expressions modulo 1000003 (106 + 3) such that if all its brackets are removed, it becomes equal to the input string (character-by-character).

输出一个整数，表示满足以下条件的不同无歧义算术表达式的数量（对 $1000003$（即 $10^6 + 3$）取模）：若将该表达式中的所有括号全部移除，则其结果字符串与输入字符串（逐字符比对）完全相同。

For the first example, the two possible unambiguous arithmetic expressions are:

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

For the second example, the three possible unambiguous arithmetic expressions are:

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

对于第一个例子，两种可能的无歧义算术表达式为：

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

对于第二个例子，三种可能的无歧义算术表达式为：

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