AT_abc418_d [ABC418D] XNOR Operation

> この問題は G 問題の部分問題です。 `0` と `1` からなる空でない文字列 $ S $ が次の条件を満たす時、 $ S $ を美しい文字列と呼びます。 - (条件) 次の一連の操作を $ S $ の長さが $ 1 $ になるまで行い、 $ S $ に残った唯一の文字を `1` にすることができる。 1. $ 1 \leq i \leq |S| - 1 $ を満たす整数 $ i $ を自由に選ぶ。 2. 整数 $ x $ を次のように定義する。 - $ S_i = $ `0` かつ $ S_{i+1}= $ `0` である場合、 $ x = 1 $ とする。 - $ S_i = $ `0` かつ $ S_{i+1}= $ `1` である場合、 $ x = 0 $ とする。 - $ S_i = $ `1` かつ $ S_{i+1}= $ `0` である場合、 $ x = 0 $ とする。 - $ S_i = $ `1` かつ $ S_{i+1}= $ `1` である場合、 $ x = 1 $ とする。 3. $ S_i $ と $ S_{i+1} $ を取り除き、それらがあった場所に $ x $ を数字とみなしたものを $ 1 $ 個挿入する。 例えば $ S= $ `10101` に対して $ i=2 $ を選んで操作を行った場合、操作後の文字列は `1001` になる。 `0` と `1` からなる長さ $ N $ の文字列 $ T $ があります。 $ T $ の部分文字列である美しい文字列の個数を求めてください。ただし、 $ 2 $ つの部分文字列が文字列として同じでも、取り出す位置が異なるならば別々に数えます。 部分文字列とは $ S $ の**部分文字列**とは、 $ S $ の先頭から $ 0 $ 文字以上、末尾から $ 0 $ 文字以上削除して得られる文字列のことをいいます。 例えば、`10` は `101` の部分文字列ですが、`11` は `101` の部分文字列ではありません。

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

$ T $ の部分文字列である美しい文字列の個数を出力せよ。

### Sample Explanation 1 $ T $ の $ 1 $ 文字目から $ 2 $ 文字目までを取り出してできる文字列 `11` は美しい文字列です。なぜならば、 $ i=1 $ として操作を行うと、操作後の文字列は `1` になるからです。 $ T $ の部分文字列である美しい文字列は次の $ 3 $ 個です。 - $ T $ の $ 1 $ 文字目を取り出してできる文字列 `1` - $ T $ の $ 2 $ 文字目を取り出してできる文字列 `1` - $ T $ の $ 1 $ 文字目から $ 2 $ 文字目までを取り出してできる文字列 `11` ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ N $ は整数 - $ T $ は `0` と `1` からなる長さ $ N $ の文字列