You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

如遇危险, 请及时拨打 110

题目描述

设 $S$ 是字符串 110 的 $10^{10}$ 份的连接。(也就是 $10000000000$ 个 110 连接在一起）。

我们有一个长度为 $N$ 的字符串 $T$。

求$T$作为连续子串出现在$S$中的次数。

输入格式

第一行一个整数 $n$, 表示 $T$ 字符串的字符个数

第二行 $n$ 个由 0 或 1 组成的字符串 $T$

输出格式

打印 $T$ 作为连续子串出现在 $S$ 中的次数。

样例 #1

样例输入 #1

4
1011

样例输出 #1

9999999999

样例 #2

样例输入 #2

22
1011011011011011011011

样例输出 #2

9999999993

提示

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