题目描述

设$S$是字符串110的$10^{10}$个副本的串联。（例如，110的$3$个副本的串联为110110110。）

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

计算$T$作为$S$的连续子串出现的次数。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $T$是长度为$N$且仅由字符0和1组成的字符串。

输入

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

$N$ $T$

输出

输出$T$作为$S$的连续子串出现的次数。

示例输入1

4
1011

示例输出1

9999999999

$S$非常长，所以我们可以在110110110（即110的$3$个副本的串联）中计算1011出现的次数。可以看出它出现了两次：

• $1$ 1011 $0110$

• $1101$ 1011 $0$

示例输入2

22
1011011011011011011011

示例输出2

9999999993