← 返回题目列表

Codeforces · 115/D

D. 明确的算术表达式

中文机器翻译题面 查看原题

让我们定义一个明确的算术表达式 (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

注意

对于第一个示例,两个可能的明确算术表达式是:

对于第二个示例,三个可能的明确算术表达式是: