

Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
どの桁も 0 ではないような正整数 X に対して,次の手順により正整数 Y を得ることを考えます:
- 文字列 S を空文字列で初期化する.
- X の桁数を N とするとき,i = 1, \ldots, N の順に次を行う:X の 10 進法表記の i 文字目を,S の先頭または末尾に挿入する.
- 文字列 S が表す正整数を Y とする.
この手順により X から得ることが可能な正整数のうちで,最小のものを f(X) と書くことにします.
どの桁も 0 ではないような正整数 Y が与えられます.どの桁も 0 ではないような正整数 X であって f(X) = Y を満たすものの個数を 998244353 で割った余りを答えてください.
制約
- Y はどの桁も 0 ではないような正整数
- 1\leq Y < 10^{200000}
入力
入力は以下の形式で標準入力から与えられます.
Y
出力
どの桁も 0 ではないような正整数 X であって f(X) = Y を満たすものの個数を 998244353 で割った余りを出力してください.
入力例 1
1332
出力例 1
3
条件を満たす X は,1332, 3132, 3312 の 3 個です.
入力例 2
3312
出力例 2
0
入力例 3
12234433442
出力例 3
153
Score : 800 points
Problem Statement
For a positive integer X none of whose digits is 0, consider obtaining a positive integer Y as follows.
- Initialize S as an empty string.
- Let N be the number of digits in X. For i = 1, \ldots, N in this order, do the following: insert the i-th character in the decimal notation of X at the beginning or end of S.
- Let Y be the positive integer represented by the string S.
Let f(X) denote the minimum positive integer that can be obtained from X in this way.
You are given a positive integer Y none of whose digits is 0. Print the number, modulo 998244353, of positive integers X none of whose digits is 0 such that f(X) = Y.
Constraints
- Y is a positive integer none of whose digits is 0.
- 1\leq Y < 10^{200000}
Input
The input is given from Standard Input in the following format:
Y
Output
Print the number, modulo 998244353, of positive integers X none of whose digits is 0 such that f(X) = Y.
Sample Input 1
1332
Sample Output 1
3
Three integers, 1332, 3132, and 3312, satisfy the conditions.
Sample Input 2
3312
Sample Output 2
0
Sample Input 3
12234433442
Sample Output 3
153