题目描述

110 を $10^{10}$ 個連結した文字列を $S$ とします（たとえば 110 を $3$ 個連結した文字列は 110110110 です）。

長さ $N$ の文字列 $T$ があります。

$S$ に $T$ が連続する部分文字列としていくつ含まれるかを求めてください。

输入格式

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

$N$ $T$

输出格式

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

4
1011

9999999999

22
1011011011011011011011

9999999993

提示

制約

• $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 が連続する部分文字列として含まれています。