← 返回题目列表

Codeforces · 1038/F

F. 环绕

中文机器翻译题面 查看原题

给你一个二进制字符串$$$s$$$。

查找长度为 $$$n$$$ 且包含 $$$s$$$ 作为子串的不同循环二进制字符串的数量。

如果字符串 $$$t$$$ 存在某种循环移位,则循环字符串 $$$t$$$ 包含 $$$s$$$ 作为子字符串,使得 $$$s$$$ 是 $$$t$$$ 循环移位的子字符串。

例如,循环字符串“000111”包含子字符串“001”、“01110”和“10”,但不包含“0110”和“10110”。

如果两个循环字符串作为字符串彼此不同,则称为不同。例如,彼此相差循环移位的两个不同串仍被视为不同的循环串。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 40$$$) — 目标字符串 $$$t$$$ 的长度。

下一行包含字符串 $$$s$$$ ($$$1 \le |s| \le n$$$) — 该字符串必须是循环字符串 $$$t$$$ 的子字符串。字符串 $$$s$$$ 仅包含字符“0”和“1”。

输出

打印唯一的整数 - 不同循环二进制字符串 $$$t$$$ 的数量,其中包含 $$$s$$$ 作为子字符串。

示例

输入 #1

2
0

输出 #1

3

输入 #2

4
1010

输出 #2

2

输入 #3

20
10101010101010

输出 #3

962

注意

在第一个示例中,存在三个循环字符串,其中包含“0”——“00”、“01”和“10”。

在第二个示例中,只有两个这样的字符串 - “1010”、“0101”。