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 @若如初见

题目描述

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 $ ( $ 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.

输出格式

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

输入输出样例

输入样例 #1

1+2*3

输出样例 #1

2

输入样例 #2

03+-30+40

输出样例 #2

3

输入样例 #3

5//4

输出样例 #3

0

输入样例 #4

5/0

输出样例 #4

1

输入样例 #5

1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

输出样例 #5

100728

说明

For the first example, the two possible unambiguous arithmetic expressions are: ` $ ((1)+(2))*(3) $ <br></br> $ (1)+((2)*(3)) $ `For the second example, the three possible unambiguous arithmetic expressions are: ` $ (03)+((-(30))+(40)) $ <br></br> $ (03)+(-((30)+(40))) $ <br></br> $ ((03)+(-(30)))+(40) $ `