AT_abc338_g [ABC338G] evall

[problemUrl]: https://atcoder.jp/contests/abc338/tasks/abc338_g 文字列 $ 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 $ の中で数字でない文字どうしが隣接することはない。 ### Sample Explanation 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 $ です。