← 返回题目列表

AtCoder · abc224_f

I. + 分隔数字的问题

中文机器翻译题面 查看原题

分数: 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.