F - 式の評価 解説 /

実行時間制限: 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.