#include <bits/stdc++.h>
using namespace std;
long long gi() {
  char cc = getchar();
  long long cn = 0, flus = 1;
  while (cc < '0' || cc > '9') {
    if (cc == '-') flus = -flus;
    cc = getchar();
  }
  while (cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
  return cn * flus;
}
const long long N = 40 + 5;
long long n, m, Ans, nxt[N][2], f[N], dp[N][N][N];
char s[N];
void inc(long long &x, long long y) { (x += y); }
signed main() {
  n = gi(), scanf("%s", s + 1), m = strlen(s + 1);
  for (register long long i = (1); i <= (m); ++i) s[i] -= '0';
  for (register long long i = (1); i <= (m); ++i) nxt[i - 1][s[i]] = i;
  for (register long long i = (1); i <= (m); ++i) {
    if (i != 1) f[i] = nxt[f[i - 1]][s[i]];
    nxt[i][s[i + 1] ^ 1] = nxt[f[i]][s[i + 1] ^ 1];
  }
  Ans = (1ll << n);
  for (register long long i = (0); i < (m); ++i) {
    memset(dp, 0, sizeof(dp)), dp[0][0][i] = 1;
    for (register long long j = (1); j <= (n); ++j)
      for (register long long k = (0); k < (m); ++k)
        for (register long long l = (0); l < (m); ++l)
          for (register long long c = (0); c <= (1); ++c)
            inc(dp[j][nxt[k][c]][nxt[l][c]], dp[j - 1][k][l]);
    Ans -= dp[n][i][i];
  }
  cout << Ans << endl;
  return 0;
}
