给你一个二进制字符串$$$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”。