Problem Background

Ysuperman particularly enjoys playing with numbers.

Originally, this problem was intended to be named "亦旧亦久罢以龄" (Eternal and Timeless), but since other problem titles are only two characters long, a longer name wouldn't be suitable.

Problem Description

During his leisure time, Ysuperman chooses to pass the time using a calculator. He inputs a very long decimal number $S$. Specifically, $S$ has $n$ digits. For clarity, let the digit at the $i$-th position from the least significant digit be $S_i$ (with indexing starting from 1).

Ysuperman will select a non-zero digit to perform a "rounding" operation. Specifically, if the $i$-th digit is chosen for rounding:

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

After several operations, $S$ will eventually become zero. The question is, how many different ways are there to reduce $S$ to zero? Two methods are considered different if and only if the position of the operation chosen differs at some step.

Input Format

A high-precision number $S$.

Output Format

The number of different ways to reduce $S$ to zero, modulo $998244353$.

Sample Input and Output

Sample Input #1

5

Sample Output #1

1

Sample Input #2

45

Sample Output #2

2

Sample Input #3

55

Sample Output #3

4

Sample Input #4

3333

Sample Output #4

24

Sample Input #5

999999

Sample Output #5

16336

Sample Input #6

1919810

Sample Output #6

3461

Sample Input #7

11451419

Sample Output #7

210000

Notes

Sample Explanation

Sample Explanation #1

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

There is 1 way.

Sample Explanation #2

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

$4\underline{5} \to \underline{5}0 \to \underline{1}00 \to 0$

There are 2 ways.

Sample Explanation #3

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

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

$\underline{5}5 \to 10\underline{5} \to 1\underline{1}0 \to \underline{1}00 \to 0$

$5\underline{5} \to \underline{6}0 \to \underline{1}00 \to 0$

There are 4 ways.

Data Range

This problem uses batched testing.

For $100\%$ of the data, $1 \leq n \leq 64$ and $S$ does not have leading zeros.

Hints

The time limit for this problem is $1145ms$.

The problem is not difficult.

见题面 Input 部分

见题面 Output 部分