TsiYing gives you a non-negative integer n. You want to divide this number into several non-negative integers according to the number of digits (it can’t be empty, but it can have some leading zeros). If k non negative integers are divided, let the sum of all digits of the i th non-negative integer be ci , then you want to satisfy ci ≡ ck+1−i (mod 2) for any i ∈ [1, k]. You need to fifind the number of legal segmentation schemes.
Smart you expected that the answer might be very large, so you only needed to output the modulo value of 998244353.
输入描述:
A non-negative integer n (0 ≤ n ≤ 1010000), the input is guaranteed not to contain leading zeros.
输出描述:
The number of legal segmentation schemes is the modulo value of 998244353.
示例1
说明
For the sample in the title, there are three legal segmentation methods:
114
1 14
11 4