大量的 110

时间限制：2s
空间限制：1024MB

题目描述

把字符串 110 连续拼接 $10^{10}$ 次得到字符串 $S$。给定长度为 $N$ 的二进制字符串 $T$，求 $T$ 在 $S$ 中作为连续子串出现的次数。

输入格式

第一行一个整数 $N$，第二行字符串 $T$。

输出格式

输出 $T$ 在 $S$ 中出现的次数。

样例输入 1

4
1011

样例输出 1

9999999999

样例输入 2

22
1011011011011011011011

样例输出 2

9999999993

数据范围

对于所有数据，$1\le N\le2\times10^5$，$T$ 只含 0 和 1。