无歧义算术表达式

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

定义无歧义算术表达式（UAE）：

• 任意非负整数都是 UAE，整数允许前导零；
• 若 $X,Y$ 是 UAE，则 $(X)+(Y)$、$(X)-(Y)$、$(X)*(Y)$、$(X)/(Y)$ 是 UAE；
• 若 $X$ 是 UAE，则 $-(X)$ 与 $+(X)$ 是 UAE。

给定一个只包含数字、+、-、*、/ 的字符串。求不同 UAE 的数量，使其删去全部括号后与给定字符串逐字符相同。答案对 $1000003$ 取模。

输入格式

一行非空字符串 $s$，不含空格。

输出格式

输出符合条件的 UAE 数量对 $1000003$ 取模后的结果。

样例输入 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

数据范围

• $1\le |s|\le2000$。

计分方式

本题按测试点独立计分，同一子任务中的测试点等分。