AT_arc110_b [ARC110B] Many 110

[problemUrl]: https://atcoder.jp/contests/arc110/tasks/arc110_b `110` を $ 10^{10} $ 個連結した文字列を $ S $ とします（たとえば `110` を $ 3 $ 個連結した文字列は `110110110` です）。 長さ $ N $ の文字列 $ T $ があります。 $ S $ に $ T $ が連続する部分文字列としていくつ含まれるかを求めてください。

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

$ S $ に $ T $ が連続する部分文字列としていくつ含まれるかを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ T $ は `0`, `1` からなる長さ $ N $ の文字列 ### Sample Explanation 1 $ S $ は長いので、`110` を $ 3 $ 個連結した `110110110` に `1011` がいくつ含まれるかを考えます。 すると、 - $ 1 $ `1011` $ 0110 $ - $ 1101 $ `1011` $ 0 $ の $ 2 $ 箇所に、`1011` が連続する部分文字列として含まれています。