AT_abc433_f [ABC433F] 1122 Subsequence 2

You are given a string $ S $ consisting of digits. A string $ T $ is called a **1122-string** if it satisfies all of the following conditions. (The definition is the same as in Problem C.) - $ T $ is a non-empty string consisting of digits. - $ |T| $ is even, where $ |T| $ denotes the length of string $ T $ . - All characters from the $ 1 $ -st through the $ \frac{|T|}2 $ -th character of $ T $ are the same digit. - All characters from the $ (\frac{|T|}2+1) $ -th through the $ |T| $ -th character of $ T $ are the same digit. - Adding $ 1 $ to the digit of the $ 1 $ -st character of $ T $ gives the digit of the $ |T| $ -th character. For example, `1122`, `01`, and `444555` are 1122-strings, but `1222` and `90` are not 1122-strings. Find the number, modulo $ 998244353 $ , of **(not necessarily contiguous) subsequences** of $ S $ that are 1122-strings. Two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

The input is given from Standard Input in the following format: > $ S $

Output the number, modulo $ 998244353 $ , of subsequences of $ S $ that are 1122-strings.

### Sample Explanation 1 The following five subsequences satisfy the condition. - `12` extracted from the $ 1 $ -st and $ 3 $ -rd characters of $ S $ - `12` extracted from the $ 1 $ -st and $ 4 $ -th characters of $ S $ - `12` extracted from the $ 2 $ -nd and $ 3 $ -rd characters of $ S $ - `12` extracted from the $ 2 $ -nd and $ 4 $ -th characters of $ S $ - `1122` extracted from the $ 1 $ -st through $ 4 $ -th characters of $ S $ Thus, output $ 5 $ . Note that two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings. ### Sample Explanation 2 There may be no subsequence that is a 1122-string. ### Constraints - $ S $ is a string consisting of digits with length between $ 1 $ and $ 10^6 $ , inclusive.