#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")

#define ll long long

#define sl(n) scanf("%lld", &n)
#define ss(n) scanf("%s", n)
#define sch(n) scanf("%c", &n)
#define sf(n) scanf("%lf", &n)

#define PI 2*acos(0.0)
#define INF (1LL<<62)

#define pll pair<ll,ll>

#define pb push_back
#define eb emplace_back
#define fr first
#define sc second
#define srt(v) sort(v.begin(), v.end())
using namespace std;

char s[20];
ll len;

ll dp[17][17];
ll solve(ll rowLeft, ll pos) {
    if (pos == len - 1) {
        return 1;
    }

    ll &ret = dp[rowLeft][pos];

    if (ret != -1) return ret;

    ret = 0;
    ret += solve(rowLeft, pos + 1);
    if (rowLeft > 1) {
        ret += solve(rowLeft - 1, pos + 1);
    }

//    cout << rowLeft << " " << pos << " " << ret << endl;

    return ret;
}

int main() {
    ll n;
    sl(n);
    ss(s);
    len = strlen(s);

    ll ans = 0;

    if (n - len > 0) {
        ans += (1LL << (len-1));
        ans *= n - len;
    }

//    cout << ans << endl;

    memset(dp, -1, sizeof(dp));

    ll rowLeft = min(n, len);
    while (rowLeft) {
        ans += solve(rowLeft--, 0);
    }

    printf("%lld\n", ans);

    return 0;
}