AT_abc338_g.[ABC338G] evall

给定一个字符串 $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}) = 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 \leq |S| \leq 10^6$
• $S$ 的每个字符都是 123456789+* 中的一个字符。
• $S$ 的首尾字符都是数字。
• $S$ 中不会有两个非数字字符相邻。

样例解释 1

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

由 ChatGPT 4.1 翻译