CF1038F.Wrap Around

You are given a binary string $s$.

Find the number of distinct cyclical binary strings of length $n$ which contain $s$ as a substring.

The cyclical string $t$ contains $s$ as a substring if there is some cyclical shift of string $t$, such that $s$ is a substring of this cyclical shift of $t$.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.

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

求长度为 $n$ 的、互不相同的循环二进制字符串中，有多少个字符串包含 $s$ 作为其子串。

循环字符串 $t$ 包含 $s$ 作为子串，当且仅当存在 $t$ 的某个循环移位，使得 $s$ 是该循环移位后的字符串的一个子串。

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

若两个循环字符串作为普通字符串彼此不同，则称它们是不同的循环字符串。例如，两个仅通过循环移位相互得到的不同字符串，仍被视为不同的循环字符串。

The first line contains a single integer $n$ ($1 \le n \le 40$) — the length of the target string $t$.

The next line contains the string $s$ ($1 \le |s| \le n$) — the string which must be a substring of cyclical string $t$. String $s$ contains only characters '0' and '1'.

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

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

Print the only integer — the number of distinct cyclical binary strings $t$, which contain $s$ as a substring.

输出唯一的整数——包含 $s$ 作为子串的不同循环二进制字符串 $t$ 的数量。

In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".

在第一个例子中，有三个包含“0”的循环字符串——“00”、“01”和“10”。

在第二个例子中，仅有两个这样的字符串——“1010”、“0101”。