Description

Linear map 可看作一个字符串，每个字符都是一个 $0\sim 9$ 的数字。

MF 认为，如果一个字符串存在两段长度均 $>1$ 的不同区间的和相同，那么该字符串是无趣的。

比如，$3421$ 就是无趣的字符串，因为 $3+4=4+2+1$，而 $5023$ 也是无趣的字符串，因为 $5+0=2+3$。相反，$13$ 和 $285$ 都不是无趣的字符串。

MF 打算将 Linear map 划分为若干非空连续且不重复的子段，这些子段包含了整个字符串的所有字符，且满足每个子段都不是无趣的字符串。

MF 是一个有趣的人，于是它想算出划分的方案数，并对 $998244353$ 取模。

Input Format

一行一个字符串 $s$。

Output Format

一行一个整数表示答案对 $998244353$ 取模后的结果。

453

4

3333

5

9475739582850286

9360

Hint

样例解释

• 样例 $\tt\#1$

所有划分均合法：$\{453\},\{45,3\},\{4,53\},\{4,5,3\}$。

• 样例 $\tt\#2$

合法方案为：$\{33,33\},\{33,3,3\},\{3,33,3\},\{3,3,33\},\{3,3,3,3\}$。

数据范围

对于 $100\%$ 的数据，满足 $1\le |s|\le 1.5\times 10^7$，且 $s$ 中仅包含数字。