Background

Please note the special time limit of this problem, and use faster input/output methods as appropriate.

In the vast world of florr, there is an unknown corner. It was built to make it easy to quickly test new mobs. Now it has been abandoned, but it has not disappeared.

The adventurer MF found this place and discovered its name: Linear map.

Problem Description

Linear map can be seen as a string, where each character is a digit from $0\sim 9$.

MF thinks that if a string has two different intervals, both with length $>1$, whose digit sums are equal, then this string is boring.

For example, $3421$ is a boring string because $3+4=4+2+1$, and $5023$ is also a boring string because $5+0=2+3$. In contrast, $13$ and $285$ are not boring strings.

MF plans to split Linear map into several non-empty, continuous, and non-overlapping segments. These segments cover all characters of the string, and every segment must not be a boring string.

MF is an interesting person, so it wants to count the number of valid splitting ways, modulo $998244353$.

Input Format

One line containing a string $s$.

Output Format

One line containing an integer, the answer modulo $998244353$.

453

4

3333

5

9475739582850286

9360

Hint

Sample Explanation

• Sample $\tt\#1$

All splits are valid: $\{453\},\{45,3\},\{4,53\},\{4,5,3\}$.

• Sample $\tt\#2$

The valid splits are: $\{33,33\},\{33,3,3\},\{3,33,3\},\{3,3,33\},\{3,3,3,3\}$.

Constraints

For $100\%$ of the data, $1\le |s|\le 1.5\times 10^7$, and $s$ contains only digits.

Translated by ChatGPT 5