分数: 500 点
问题陈述
给定的是一个字符串 S 由以下数字组成 1 通过 9.
来自该字符串 S,让我们做一个公式 T 通过以下操作。
- 最初,让 T=S.
- 选择一个(可能是空的)集合 A 不同的整数,其中每个元素位于 1 和 |S|-1 (含)。
- 对于每个元素 x 按降序排列,执行以下操作。
- 插入
+之间 x-th 和 (x+1)第一个字符 T.
- 插入
例如,当 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
输出
打印答案。
示例输入 1
1234
示例输出 1
1736
有八个公式可以得到: T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34,和 1+2+3+4.
这些公式的评估总和为 1736.
示例输入 2
1
示例输出 2
1
S 的长度可能为 1,在这种情况下唯一可能的选择 A 是空集。
示例输入 3
31415926535897932384626433832795
示例输出 3
85607943
一定要找到模数之和 998244353.