让我们定义一个明确的算术表达式 (UAE),如下所示。
- 所有非负整数都是 UAE 的。整数可以有前导零(例如,0000 和 0010 被视为有效整数)。
- 如果 X 和 Y 是两个 UAE,则“(X) + (Y)”、“(X) - (Y)”、“(X) * (Y)”和“(X) / (Y)”(均不带双引号)是 UAE。
- 如果 X 是阿联酋,则“ - (X)”和“ + (X)”(均不带双引号)是阿联酋的。您将得到一个仅由数字 (“0” - “9”) 和字符“-”、“+”、“*”和“/”组成的字符串。您的任务是计算不同的可能的明确算术表达式的数量,这样,如果删除该明确算术表达式的所有括号(字符“(”和“)”),它就成为输入字符串。由于答案可能非常大,因此打印它模 1000003 (106 + 3)。
输入
第一行是一个非空字符串,由数字 ('0'-'9') 和字符 '-'、'+'、'*' 和/或 '/' 组成。它的长度不会超过2000。该行不包含任何空格。
输出
打印一个整数,表示不同的明确算术表达式的数量以 1000003 (106 + 3) 为模,这样,如果删除所有括号,它就等于输入字符串(逐个字符)。
示例
输入 #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
注意
对于第一个示例,两个可能的明确算术表达式是:
对于第二个示例,三个可能的明确算术表达式是: