Score : $500$ points

问题描述

给定一个由 $1$ 到 $9$ 的数字组成的字符串 $S$。

从该字符串 $S$ 中，我们按照以下操作构建一个公式 $T$：

• 首先，令 $T=S$。
• 选择一个（可能为空）的整数集合 $A$，其中每个元素都在 $1$ 和 $|S|-1$（包括两端点）之间，并且所有元素互不相同。
• 按降序遍历集合 $A$ 中的每个元素 $x$，执行以下操作：
  • 在 $T$ 的第 $x$ 个字符和第 $(x+1)$ 个字符之间插入一个 + 符号。

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

考虑通过这些操作得出的所有可能的公式 $T$ 的计算结果。求这些计算结果之和对 $998244353$ 取模后的值。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 09:52:00