E - Deque Minimization 解説 /

実行時間制限: 5 sec / メモリ制限: 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