环绕匹配

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一个二进制字符串 $s$。求有多少个长度为 $n$ 的不同二进制字符串 $t$，把 $t$ 看成循环字符串后包含 $s$ 作为子串。

如果存在 $t$ 的某个循环移位，使得 $s$ 是该移位字符串的子串，就称循环字符串 $t$ 包含 $s$。例如，循环字符串 000111 包含 001、01110 和 10，但不包含 0110 和 10110。

两个字符串只要本身不同，就被视为不同答案；即使它们仅相差一次循环移位，也仍分别计数。

输入格式

第一行一个整数 $n$，表示目标字符串长度。

第二行一个仅含 0、1 的字符串 $s$。

输出格式

输出满足条件的字符串数量。

样例输入 1

2
0

样例输出 1

3

样例输入 2

4
1010

样例输出 2

2

样例输入 3

20
10101010101010

样例输出 3

962

数据范围

对于所有数据，$1\le |s|\le n\le40$。

每个测试点独立计分。