102245: [AtCoder]ABC224 F - Problem where +s Separate Digits

Problem Statement

Given is a string $S$ consisting of digits from $1$ through $9$.
From this string $S$, let us make a formula $T$ by the following operations.

• Initially, let $T=S$.
• Choose a (possibly empty) set $A$ of different integers where each element is between $1$ and $|S|-1$ (inclusive).
• For each element $x$ in descending order, do the following.
  • Insert a + between the $x$-th and $(x+1)$-th characters of $T$.

For example, when $S=$ 1234 and $A= \lbrace 2,3 \rbrace$, we will have $T$= 12+3+4.

Consider evaluating all possible formulae $T$ obtained by these operations. Find the sum, modulo $998244353$, of the evaluations.

Constraints

• $1 \le |S| \le 2 \times 10^5$
• $S$ consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the answer.

Sample Input 1

1234

Sample Output 1

1736

There are eight formulae that can be obtained as $T$: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is $1736$.

Sample Input 2

1

Sample Output 2

1

$S$ may have a length of $1$, in which case the only possible choice for $A$ is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo $998244353$.

问题描述

给定一个由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$

输出

打印答案。

样例输入 1

1234

样例输出 1

1736

可以得到8个不同的公式$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$。