F - 分离数字的问题

得分：$500$分

问题描述

给定一个由数字$1$到$9$组成的字符串$S$。
从这个字符串$S$中，我们通过以下操作得到一个公式$T$。

• 初始时，令$T=S$。
• 选择一个（可能为空）的不同整数集合$A$，其中每个元素介于$1$和$|S|-1$之间（包括端点）。
• 对于每个递减的元素$x$，执行以下操作。
  • 在$T$的第$x$个和第$(x+1)$个字符之间插入一个+。

例如，当$S=$ 1234且$A= \lbrace 2,3 \rbrace$时，我们会得到$T$= 12+3+4。

考虑评估通过这些操作获得的所有可能的公式$T$。求其评估结果的和，模$998244353$。

约束

• $1 \le |S| \le 2 \times 10^5$
• $S$由1, 2, 3, 4, 5, 6, 7, 8和9组成。

输入

输入以以下格式给出。

$S$

输出

输出答案。

1234

1736

可以得到八个公式$T$： 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34和1+2+3+4。
这些公式的评估结果的和为$1736$。

1

1

$S$可能的长度为$1$，此时$A$的唯一选择是空集。

31415926535897932384626433832795

85607943

请确保将和对$998244353$取模。