Background

Ysuperman especially likes playing counting games.

Actually, this problem was originally planned to be called “亦旧亦久罢以龄”, but I saw that other problem names are all two characters long, so it would not be good to use such a long name.

Problem Description

In his free time, Ysuerpman chooses to kill time with a calculator. He inputs a very long decimal number $S$. How long is it? It has $n$ digits in total. For convenience, let the digit on the $i$-th position from low to high be $S_i$ (the index starts from $1$).

Each time, Ysuerpman will choose a non-zero digit position and perform “rounding”. Specifically, suppose he performs “rounding” on the $i$-th digit:

• If $S_i<5$, then subtract $S_i \cdot 10^{i-1}$ from $S$.
• If $S_i\ge5$, then add $10^i$ to $S$, and then subtract $S_i \cdot 10^{i-1}$.

After several operations, $S$ will always become $0$. Now the question is: how many different plans are there that make $S$ become $0$? Two plans are different if and only if there exists some operation where the chosen digit position is different.

Input Format

A high-precision number $S$.

Output Format

The number of different plans that make $S$ become $0$, modulo $998244353$.

5

1

45

2

55

4

3333

24

999999

16336

1919810

3461

11451419

210000

Hint

Sample Explanation

Sample Explanation $1$

$\underline5\to \underline10 \to 0$

There is $1$ plan in total.

Sample Explanation $2$

$\underline{4}5\to\underline{5}\to\underline10\to 0$

$4\underline{5}\to\underline{5}0\to \underline100 \to 0$

There are $2$ plans in total.

Sample Explanation $3$

$\underline{5}5\to\underline{1}05\to\underline{5}\to\underline{1}0 \to 0$

$\underline{5}5\to10\underline{5}\to\underline{1}10\to \underline10 \to 0$

$\underline{5}5\to10\underline{5}\to1\underline{1}0\to \underline100 \to 0$

$5\underline{5}\to\underline{6}0\to \underline100 \to 0$

There are $4$ plans in total.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $1\le n \le 64$, and $S$ has no leading zeros.

Hint

The time limit for this problem is $1145\ \rm{ms}$.

The problem is not hard.

Translated by ChatGPT 5