AT_arc110_b [ARC110B] Many 110

将 `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$ 的字符串 ### 样例解释 1 由于 $S$ 很长，我们可以考虑将 `110` 连接 $3$ 次得到的 `110110110` 中包含多少个 `1011`。可以发现： - $1$ `1011` $0110$ - $1101$ `1011` $0$ 在这 $2$ 个位置，`1011` 作为连续的子串出现在字符串中。 由 ChatGPT 4.1 翻译