AT_abc433_f [ABC433F] 1122 Subsequence 2

数字からなる文字列 $ S $ が与えられます。 以下の条件を全て満たす文字列 $ T $ を **1122文字列** と呼びます。（定義は C 問題と同じです。） - $ T $ は数字からなる空でない文字列 - $ |T| $ は偶数。ここで、 $ |T| $ は文字列 $ T $ の長さを表す - $ T $ の $ 1 $ 文字目から $ \frac{|T|}2 $ 文字目までは全て同じ数字である - $ T $ の $ \frac{|T|}2+1 $ 文字目から $ |T| $ 文字目までは全て同じ数字である - $ T $ の $ 1 $ 文字目の数字に $ 1 $ を足すと $ |T| $ 文字目の数字になる 例えば `1122` や `01` 、 `444555` などは 1122文字列 ですが、 `1222` や `90` は 1122文字列 ではありません。 $ S $ の **（連続でなくても良い）部分列** であって 1122文字列 であるものの個数を $ 998244353 $ で割ったあまりを求めてください。 ただし、ある二つの部分列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。

入力は以下の形式で標準入力から与えられる。 > $ S $

$ S $ の部分列であって 1122文字列 であるものの個数を $ 998244353 $ で割ったあまりを出力せよ。

### Sample Explanation 1 以下の $ 5 $ つの部分列が条件を満たします。 - $ S $ の $ 1 $ 文字目と $ 3 $ 文字目を取り出した `12` - $ S $ の $ 1 $ 文字目と $ 4 $ 文字目を取り出した `12` - $ S $ の $ 2 $ 文字目と $ 3 $ 文字目を取り出した `12` - $ S $ の $ 2 $ 文字目と $ 4 $ 文字目を取り出した `12` - $ S $ の $ 1 $ 文字目から $ 4 $ 文字目を取り出した `1122` したがって、 $ 5 $ を出力してください。 文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。 ### Sample Explanation 2 1122文字列 となる部分列が存在しない場合もあります。 ### Constraints - $ S $ は長さ $ 1 $ 以上 $ 10^6 $ 以下の数字からなる文字列