Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Codeforces Round 508 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

strings

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Wrap Around

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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'.

Output

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

Examples

Input

2

0

Output

3

Input

4

1010

Output

2

Input

20

10101010101010

Output

962

Note

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".

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/01/2023 07:23:30 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|