実行時間制限: 2 sec / メモリ制限: 1024 MB
問題文
数字と *
(乗算記号)からなる文字列 S が与えられます。
S を数式として見た上で、その式を評価した値を 998244353 で割った余りを求めてください。
例えば、S= 5*32*2
のとき、式を評価した値は 5 \times 32 \times 2 = 320 です。
なお、S は正しい数式であることが保証されます。すなわち、以下がすべて保証されます。
- S の中に
*
が連続して現れることはない - S の先頭の文字は数字である
- S の末尾の文字は数字である
制約
- S は数字と
*
からなる文字列 - S は正しい数式
- S の長さは 1 以上 10^6 以下
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
5*32*2
出力例 1
320
問題文中で説明した例の通りです。
入力例 2
998244354
出力例 2
1
S が *
を含まないこともあります。
式を評価した値を 998244353 で割った余りを求めることに注意してください。
入力例 3
05*000
出力例 3
0
S の中に現れる数が先頭に余分な 0 を含むこともあります。
Problem Statement
Given a string S consisting of digits and *
(multiplication sign),
interpret S as a mathematical expression, evaluate it, and report the result modulo 998244353.
For example, S= 5*32*2
evaluates to 5 \times 32 \times 2 = 320.
Here, it is guaranteed that S is a valid expression. In other words, it is guaranteed that:
- multiple
*
do not occur contiguously in S; - S starts with a digit;
- S ends with a digit.
Constraints
- S is a string consisting of digits and
*
. - S is a valid expression.
- S has a length between 1 and 10^6, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer as an integer.
Sample Input 1
5*32*2
Sample Output 1
320
This example is already described in the problem statement.
Sample Input 2
998244354
Sample Output 2
1
S may not contain *
.
Be sure to report the evaluated value modulo 998244353.
Sample Input 3
05*000
Sample Output 3
0
Numbers in S may have leading zeros.