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.

Input

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

The next line contains the string s (1 ≤ |s| ≤ 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".
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int n, f[];
    static String s;
    static long ans, dp[][][];

    private static void build() {
        // build failure function F[i] = index of largest prefix/suffix with end < i = where to look if i doesn't match
        f[0] = -1;
        f[1] = 0;
        for(int i = 2; i <= s.length(); i++) {
            f[i] = f[i-1];
            while(f[i] != -1 && s.charAt(i-1) != s.charAt(f[i])) f[i] = f[f[i]];
            ++f[i]; // ++ because this is on the scale of i-2 and not i-1
        }
    }

    private static int getNext(int state, char val) {
        if(state == s.length()) return getNext(f[state], val);
        int nxt = state;
        while(nxt != -1 && s.charAt(nxt) != val) nxt = f[nxt];
        return nxt + 1;
    }

    private static long calc(int n, int curr, int start, int done) {
        if(curr == s.length()) done = 1;
        if(n == 0) return (curr == start && done == 1 ? 1 : 0);

        if(dp[n][curr][done] != -1) return dp[n][curr][done];
        dp[n][curr][done] = 0;
        int nxt0 = getNext(curr, '0');
        int nxt1 = getNext(curr, '1');
        dp[n][curr][done] += calc(n-1, nxt0, start, done);
        dp[n][curr][done] += calc(n-1, nxt1, start, done);
        return dp[n][curr][done];
    }

    private static long solve(int starting_state) {
        dp = new long[n + 1][s.length() + 1][2];
        for(long[][] r1: dp) {
            for (long[] r2 : r1)
                Arrays.fill(r2, -1);
        }
        return calc(n, starting_state, starting_state, 0);
    }

    public static void main(String[] args) {
        InputReader cin = new InputReader(System.in);
        n = cin.nextInt();
        s = cin.next();
        f = new int[s.length() + 1];
        ans = 0;

        build();
        for(int starting_state = 0; starting_state <= s.length(); starting_state++) {
            ans += solve(starting_state);
        }

        System.out.println(ans);
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

