F. Поворот строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ над бинарным алфавитом.

Посчитайте количество различных циклических строк длины $$$n$$$ над бинарным алфавитом, которые содержат $$$s$$$ как подстроку.

Циклическая строка $$$t$$$ содержит $$$s$$$ как подстроку если существует какой-то циклический сдвиг строки $$$t$$$, такой что $$$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$$$ как подстроку.

Примеры
Входные данные
2
0
Выходные данные
3
Входные данные
4
1010
Выходные данные
2
Входные данные
20
10101010101010
Выходные данные
962
Примечание

В первом примере есть три циклических строки, которые содержат "0" — "00", "01" и "10".

Во втором примере есть только две такие строки — "1010", "0101".