题目描述

对于一个每一位都不是 $0$ 的正整数 $X$，我们通过以下步骤得到一个正整数 $Y$：

• 用空字符串初始化字符串 $S$。
• 设 $X$ 的位数为 $N$，对于 $i = 1, \ldots, N$，依次将 $X$ 的十进制表示的第 $i$ 位插入到 $S$ 的开头或末尾。
• 将字符串 $S$ 视为正整数，得到 $Y$。

在所有可以通过上述步骤从 $X$ 得到的正整数中，最小的记为 $f(X)$。

---

现在给定一个每一位都不是 $0$ 的正整数 $Y$。请你计算有多少个每一位都不是 $0$ 的正整数 $X$ 满足 $f(X) = Y$，并将答案对 $998244353$ 取模后输出。

输入格式

输入为标准输入，格式如下：

$Y$

输出格式

输出满足条件的每一位都不是 $0$ 的正整数 $X$ 的个数，对 $998244353$ 取模后的结果。

样例 1

输入

1332

输出

3

样例 2

输入

3312

输出

0

样例 3

输入

12234433442

输出

153

说明/提示

限制

• $Y$ 是一个每一位都不是 $0$ 的正整数
• $1 \leq Y < 10^{200000}$

样例解释 1

满足条件的 $X$ 有 $1332$、$3132$、$3312$，共 $3$ 个。

由 ChatGPT 4.1 翻译