evall（表达式求和）

题目描述

给你一个字符串 $S$。$S$ 的每个字符都是 123456789+* 中的一个，且 $S$ 的第一个和最后一个字符都是数字。$S$ 中不存在相邻的非数字字符。

对于整数对 $i, j$（$1 \le i \le j \le |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})$ 为 0。

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

输入格式

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

$S$

输出格式

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

样例

1+2*34

197

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

$\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$。

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

527930018

数据范围

• $1 \le |S| \le 10^6$
• $S$ 的每个字符都是 123456789+* 中的一个。
• $S$ 的第一个和最后一个字符都是数字。
• $S$ 中不存在相邻的非数字字符。