题目描述

给定一个只包含非负整数、加号和乘号的表达式，按先乘后加的规则计算结果，并输出结果除以 $10000$ 的余数。

输入格式

输入一行表达式，不含空格或括号。

输出格式

输出一个整数，不输出多余的前导零。

样例

1+1*3+4

8

1+1234567890*1

7891

1+1000000003*1

4

数据范围

对于 $30\%$ 的数据，运算符个数不超过 $100$；对于 $80\%$ 的数据，不超过 $1000$；对于 $100\%$ 的数据，不超过 $100000$。表达式合法，包含至少一个整数，每个整数在 $0$ 至 $2^{31}-1$ 之间。