AT_abc433_c [ABC433C] 1122 Substring 2

数字からなる文字列 $ S $ が与えられます。 以下の条件を全て満たす文字列 $ T $ を **1122文字列** と呼びます。（定義は F 問題と同じです。） - $ 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文字列 であるものの個数を求めてください。 ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。

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

$ S $ の空でない部分文字列であって 1122文字列 であるものの個数を出力せよ。

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