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

const int MAXN = 45;

char str[MAXN];
int n, L;
long long now;

int nxt[MAXN];

void solve_brute()
{
	static unordered_set<long long> st;
	static set<long long> tmp;
	for (int i = 0; i < 1<<(n-L); i++) {
		long long cur = (now<<(n-L))|i, nxt = cur;
		for (int j = 0; j < n; j++) {
			nxt = ((nxt&1)<<(n-1))|(nxt>>1);
			cur = min(cur, nxt);
		}
		st.insert(cur);
	}
	int ans = 0;
	for (auto cur : st) {
		static long long s[MAXN];
		long long nxt = cur;
		for (int j = 0; j < n; j++) {
			s[j] = nxt;
			nxt = ((nxt&1)<<(n-1))|(nxt>>1);
		}
		sort(s, s+n);
		ans += unique(s, s+n)-s;
	}
	cout << ans << endl;
}

void solve_dp()
{
	long long ans = 1ll<<n;
	for (int i = 0; i < 1<<(L-1); i++) {
		long long forbid = 1;
		for (int j = 1; j <= L-1; j++)
			if ((now&((1<<j)-1)) == (i>>(L-1-j)))
				forbid |= 1ll<<j;
		int p = 0;
		for (int j = L-2; j >= 0; j--) {
			int cur = i>>j&1;
			while (p && str[p+1] != cur) p = nxt[p];
			if (str[p+1] == cur) p++;
		}
		static long long dp[2][41];
		int now = 0, nx = 1;
		memset(dp, 0, sizeof dp);
		dp[now][p] = 1;
		for (int j = L-1; j < n; j++) {
			for (int k = 0; k < L; k++) {
				if (!dp[now][k]) continue;
				auto try_add = [&](int t) {
					int p = k;
					while (p && str[p+1] != t) p = nxt[p];
					if (str[p+1] == t) p++;
					if (p < L)
						dp[nx][p] += dp[now][k];
				};
				try_add(0);
				try_add(1);
			}
			swap(now, nx);
			memset(dp[nx], 0, sizeof dp[nx]);
		}
		/*for (int j = L-2; j >= 0; j--)
			cout << (i>>j&1);
		cout << " -- ";
		for (int j = 0; j < L; j++)
			cout << (forbid>>j&1);
		cout << endl;*/
		for (int j = 0; j < L; j++) {
			int flag = 1, pre = j;
			while (pre && flag) {
				if (forbid>>(L-pre)&1)
					flag = 0;
				pre = nxt[pre];
			}
			if (flag) 
				ans -= dp[now][j];
		}
	}
	cout << ans << endl;
}

int main()
{
	scanf("%d", &n);
	scanf("%s", str+1), L = strlen(str+1);
	nxt[1] = 0;
	int p = 0;
	for (int i = 1; i <= L; i++) {
		str[i] -= '0';
	}
	for (int i = 2; i <= L; i++) {
		while (p && str[i] != str[p+1]) p = nxt[p];
		if (str[i] == str[p+1]) p++;
		nxt[i] = p;
	}
	for (int i = 1; i <= L; i++)
		now = now*2+str[i];
	// solve_brute();
	if (n-L <= 20) solve_brute();
	else solve_dp();
	return 0;
}