题目背景

Ysuperman 特别喜欢玩数数游戏。

其实本来这题想叫“亦旧亦久罢以龄”的，但是我见到其他的题目名称都是两个字，取这么长名称也不好。

题目描述

闲暇时光，Ysuerpman 选择用计算器打发时间。他输入了一个很长的十进制数 $S$。具体有多长呢？共 $n$ 位。为了方便解释，设从低到高第 $i$ 位上的数字是 $S_i$（下标从 $1$ 开始）。

Ysuerpman 每次会选择一个非零数字位进行「四舍五入」。具体来说，假设「四舍五入」的是第 $i$ 位：

• 如果 $S_i<5$，则让 $S$ 减去 $S_i \cdot 10^{i-1}$。
• 如果它 $S_i\ge5$，则让 $S$ 加上 $10^i$ 再减去 $S_i \cdot 10^{i-1}$。

经过若干次操作后，$S$ 总会变成 $0$。现在问题来了，请问有多少种使得 $S$ 变成 $0$ 的不同的方案？两个方案不同当且仅当某一次选择的操作位置不同。

输入格式

一个高精度数 $S$。

输出格式

使得 $S$ 变成 $0$ 的不同的方案数量，对 $998244353$ 取模。

5

1

45

2

55

4

3333

24

999999

16336

1919810

3461

11451419

210000

提示

样例解释

样例解释 $1$

$\underline5\to \underline10 \to 0$

共 $1$ 种。

样例解释 $2$

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

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

共 $2$ 种。

样例解释 $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$

共 $4$ 种。

数据范围

本题采用捆绑测试。

$\rm{subtask}$	$n$	$S_i\in$	分数
$0$	$\le 6$	$[0,9]$	$5$
$1$	$\le 15$		$13$
$2$	$\le40$	$[0,4]$	$5$
$3$	$\le 40$	$\{9\}$	$12$
$4$	$\le40$	$[5,8]$	$15$
$5$	$\le 40$	$[0,9]$	$30$
$6$	$\le 64$		$20$

对于 $100\%$ 的数据，满足 $1\le n \le 64$，$S$ 不含前导零。

提示

本题时间限制为 $1145ms$。

题目并不难。