CF115D Unambiguous Arithmetic Expression

对$UAE$作出如下定义： 所有的非负整数都是$UAE$。这些整数可能含有前导零（如$0000\ 0000$和$0010\ 0010$被认为是有效的整数）。如果$X$和$Y$是$UAE$，那么"$(X)+(Y)$"，"(X)-(Y)"，"$(X)* (Y)$"，"$(X)/(Y)$"都是$UAE$。（不含引号） 如果$X$是$UAE$，那么"$-(X)$"和"$+(X)$"也是$UAE$。 给出一个只由$0-9$的数字、"-"、"+"、" * "、"/"组成的字符串。你的任务是计算含有不同$UAE$表达式的数量，使得如果去掉所有的括号，这些$UAE$表达式能成为给出的输入文件中的字符串。因为答案可能非常大，请你输出对$10^6+3$取模的结果。

输入文件的第一行是一个非空的字符串，只由$0-9$的数字、"-"、"+"、" * "、"/"组成。字符串的长度不超过$2000$。字符串中不包含任何空格。

输出一行一个整数，去除所有括号后能够与输入文件中的字串相同的$UAE$表达式的个数对$10^6+3$取模的结果。 翻译By @若如初见

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) $ `