10040: ABC338 —— G - evall
[Creator : ]
Description
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$.
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 ex
- 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$.
Input
The input is given from Standard Input in the following format:
```
$S$
```
```
$S$
```
Output
The input is given from Standard Input in the following format:
```
$S$
```
```
$S$
```
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$.
- 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$.
Sample 1 Input
1+2*34
Sample 1 Output
197
The cases where eval(Si..j) is not zero are as follows:
- eval(S1..1)=1
- eval(S1..3)=1+2=3
- eval(S1..5)=1+2×3=7
- eval(S1..6)=1+2×34=69
- eval(S3..3)=2
- eval(S3..5)=2×3=6
- eval(S3..6)=2×34=68
- eval(S5..5)=3
- eval(S5..6)=34
- eval(S6..6)=4
Sample 2 Input
338*3338*33338*333338+3333338*33333338+333333338
Sample 2 Output
527930018