103386: [Atcoder]ABC338 G - evall

Problem Statement

You are given a string $S$. Each character of $S$ is one of 123456789+*, and the first and last characters of $S$ are digits. There are no adjacent non-digit characters in $S$.

For a pair of integers $i, j$ ($1 \leq i \leq j \leq |S|$), we define $\mathrm{eval}(S_{i..j})$ as follows:

• If both the $i$-th and $j$-th characters of $S$ are digits, then $\mathrm{eval}(S_{i..j})$ is the result of evaluating the $i$-th to the $j$-th characters (inclusive) of $S$ as a usual arithmetic expression (where * represents multiplication). For example, if $S =$ 1+2*151, then $\mathrm{eval}(S_{1..6}) = 1 + 2 \times 15 = 31$.
• Otherwise, $\mathrm{eval}(S_{i..j})$ is zero.

Find ${\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}$, modulo $998244353$.

Constraints

• $1 \leq |S| \leq 10^6$
• Each character of $S$ is one of 123456789+*.
• The first and last characters of $S$ are digits.
• There are no adjacent non-digit characters in $S$.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print ${\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}$, modulo $998244353$.

Sample Input 1

1+2*34

Sample Output 1

197

The cases where $\mathrm{eval}(S_{i..j})$ is not zero are as follows:

• $\mathrm{eval}(S_{1..1}) = 1$
• $\mathrm{eval}(S_{1..3}) = 1 + 2 = 3$
• $\mathrm{eval}(S_{1..5}) = 1 + 2 \times 3 = 7$
• $\mathrm{eval}(S_{1..6}) = 1 + 2 \times 34 = 69$
• $\mathrm{eval}(S_{3..3}) = 2$
• $\mathrm{eval}(S_{3..5}) = 2 \times 3 = 6$
• $\mathrm{eval}(S_{3..6}) = 2 \times 34 = 68$
• $\mathrm{eval}(S_{5..5}) = 3$
• $\mathrm{eval}(S_{5..6}) = 34$
• $\mathrm{eval}(S_{6..6}) = 4$

The sum of these is $1+3+7+69+2+6+68+3+34+4 = 197$.

Sample Input 2

338*3338*33338*333338+3333338*33333338+333333338

Sample Output 2

527930018

问题描述

你得到了一个字符串 $S$。$S$ 的每个字符都是 123456789+* 中的一个，且 $S$ 的首尾字符都是数字。$S$ 中没有相邻的非数字字符。

对于整数对 $i, j$（$1 \leq i \leq j \leq |S|$），我们定义 $\mathrm{eval}(S_{i..j})$ 如下：

• 如果 $S$ 的第 $i$ 个和第 $j$ 个字符都是数字，那么 $\mathrm{eval}(S_{i..j})$ 是将 $S$ 的第 $i$ 个到第 $j$ 个字符（含）视为一个通常的算术表达式（其中 * 代表乘法）的结果。例如，如果 $S =$ 1+2*151，那么 $\mathrm{eval}(S_{1..6}) = 1 + 2 \times 15 = 31$。
• 否则，$\mathrm{eval}(S_{i..j})$ 为零。

找到 ${\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}$，对 $998244353$ 取模。

约束

• $1 \leq |S| \leq 10^6$
• $S$ 的每个字符都是 123456789+* 中的一个。
• $S$ 的首尾字符都是数字。
• $S$ 中没有相邻的非数字字符。

输入

输入从标准输入按以下格式给出：

$S$

输出

输出 ${\displaystyle \sum_{i=1}^{|S|} \sum_{j=i}^{|S|} \mathrm{eval}(S_{i..j})}$，对 $998244353$ 取模。

样例输入 1

1+2*34

样例输出 1

197

其中 $\mathrm{eval}(S_{i..j})$ 不为零的情况如下：

• $\mathrm{eval}(S_{1..1}) = 1$
• $\mathrm{eval}(S_{1..3}) = 1 + 2 = 3$
• $\mathrm{eval}(S_{1..5}) = 1 + 2 \times 3 = 7$
• $\mathrm{eval}(S_{1..6}) = 1 + 2 \times 34 = 69$
• $\mathrm{eval}(S_{3..3}) = 2$
• $\mathrm{eval}(S_{3..5}) = 2 \times 3 = 6$
• $\mathrm{eval}(S_{3..6}) = 2 \times 34 = 68$
• $\mathrm{eval}(S_{5..5}) = 3$
• $\mathrm{eval}(S_{5..6}) = 34$
• $\mathrm{eval}(S_{6..6}) = 4$

这些的和为 $1+3+7+69+2+6+68+3+34+4 = 197$。

样例输入 2

338*3338*33338*333338+3333338*33333338+333333338

样例输出 2

527930018