Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 から 9 までの数字のみで構成された文字列 S が与えられます。
この文字列 S から、以下の操作によって式 T を作ります。
- はじめ、 T=S であるとする。
- 各要素が 1 以上 |S|-1 以下の整数である、値に重複のない集合 A を選ぶ。なお、 A が空集合であってもよい。
- A の全ての要素 x について、 x の降順に以下の操作を行う。
- T の x 文字目と x+1 文字目の間に、
+
を挿入する。
- 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
式 T としてあり得るものは 1234
, 123+4
, 12+34
, 12+3+4
, 1+234
, 1+23+4
, 1+2+34
, 1+2+3+4
の 8 つです。
これらを計算した値の総和は 1736 です。
入力例 2
1
出力例 2
1
S の長さが 1 であることもあります。この場合、 A として指定可能なのは空集合のみです。
入力例 3
31415926535897932384626433832795
出力例 3
85607943
答えを 998244353 で割った余りを求めてください。
Score : 500 points
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.
- Insert a
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
, and9
.
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.