Problem 5F. 拆分数

时间限制：1s

空间限制：256MB

Description

Zms 给你一个非负整数 n。你想将这个数直接拆分成若干个非负整数（非空但可以有前导零）。例如数字 123456 可以拆分成 12、34 和 56。如果分成了 k 个非负整数，则第 i 个非负整数的所有数字之和为 \(c_i\)，要求对于任意 i ∈ [1, k]，都满足 \(c_i ≡ c_{k+1−i} (mod 2)\)。你需要计算合法的划分方案数，结果对 998244353 取模。

注：mod 是取模运算，即取余数。例如，a mod b 表示 a 除以 b 的余数。

Input Format

第一行包含一个非负整数 \(n(0≤n≤10^{10000})\)，保证输入不包含前导零。

Output Format

输出一行一个整数 - 合法分割方案的数量，结果对99824353取模。

Input Example #1：

114

Output Example #1：

3

Data Range

\(0≤n≤10^{10000}\) 。

Note

对于样例，有三种合法的分割方法：

114
1 14
11 4