#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 65;

int n, m;
string s;
int pi[N], nxt[N][2];
ll dp[N][N];

void solve() {
    cin >> n >> s;
    m = (int)s.size();
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    for (int i = 0; i <= m; i++)
        for (int c = 0; c < 2; c++) {
            if (c == (s[i] - '0')) nxt[i][c] = i + 1;
            else if (i > 0) nxt[i][c] = nxt[pi[i - 1]][c];
        }
    ll res = 0;
    for (int k = 0; k < m; k++) {
        memset(dp, 0, sizeof dp);
        dp[0][k] = 1;
        for (int i = 0; i < n; i++) {
            for (int u = 0; u < m; u++) {
                for (int c = 0; c < 2; c++) {
                    int v = nxt[u][c];
                    if (v < m) dp[i + 1][v] += dp[i][u];
                }
            }
        }
        res += dp[n][k];
    }
    cout << (1LL << n) - res << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define TASK "PLASMID"
    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    int tests = 1; // cin >> tests;
    while (tests--) solve();

    #ifdef LOCAL
    cerr << "\nTime elapsed: " << clock() << " ms.\n";
    #endif
    return 0;
}