Non‐Boring Partitioning of a Linear Map

A linear map is represented as a string where each character is a digit from \(0\) to \(9\). A string is defined as boring if there exist two different contiguous substrings (intervals) each of length greater than 1 having the same sum of digits.

For example, the string \(3421\) is boring because \(3+4 = 4+2+1\), and \(5023\) is boring because \(5+0 = 2+3\). On the other hand, \(13\) and \(285\) are not boring.

You are given a linear map as a string. The task is to partition the string into one or more non-empty contiguous segments that cover the entire string such that:

• Each segment is non-boring.
• All segments are distinct (i.e. no two segments are identical).

Output the number of valid partitioning schemes modulo \(998244353\).

Note:

• A segment of length \(\le 2\) is automatically non-boring since it cannot have two different subintervals, each of length greater than 1.
• When checking if a segment of length at least 3 is boring, consider all contiguous subintervals of length \(\ge 2\). If there exists at least one digit sum that appears for two different intervals, the segment is boring.

inputFormat

The input consists of a single line containing the linear map, a string of digits.

outputFormat

Output a single integer, the number of valid partitioning schemes, taken modulo \(998244353\).

sample

13

2