题目描述

将 110 连接 $10^{10}$ 次得到字符串 $S$（例如，将 110 连接 $3$ 次得到的字符串为 110110110）。

给定一个长度为 $N$ 的字符串 $T$。

请你求出 $S$ 中包含多少个连续的子串等于 $T$。

输入格式

输入从标准输入中按以下格式给出。

$N$ $T$

输出格式

输出 $S$ 中包含多少个连续子串等于 $T$。

样例 1

输入

4
1011

输出

9999999999

样例 2

输入

22
1011011011011011011011

输出

9999999993

说明/提示

限制条件

• $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 翻译