#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long tot = 1;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    tot = -1;
    c = getchar();
  }
  long long sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * tot;
}
inline void wr(long long x) {
  if (x < 0) {
    putchar('-');
    wr(-x);
    return;
  }
  if (x >= 10) wr(x / 10);
  putchar(x % 10 + '0');
}
inline void wrn(long long x) {
  wr(x);
  putchar('\n');
}
inline void wri(long long x) {
  wr(x);
  putchar(' ');
}
inline void wrn(long long x, long long y) {
  wri(x);
  wrn(y);
}
inline void wrn(long long a, long long b, long long c) {
  wri(a);
  wrn(b, c);
}
long long n, m, ch[55][2], nxt[55], f[55][55][55], ans;
char st[55];
signed main() {
  n = read();
  scanf("%s", st + 1);
  m = strlen(st + 1);
  for (long long i = 1; i <= m; i++) ch[i - 1][st[i] - '0'] = i;
  for (long long i = 1; i <= m; i++)
    for (long long j = 0; j <= 1; j++)
      if (ch[i][j])
        nxt[ch[i][j]] = ch[nxt[i]][j];
      else
        ch[i][j] = ch[nxt[i]][j];
  ans = 1ll << n;
  for (long long i = (0); i <= (m - 1); i++) {
    memset(f, 0, sizeof(f));
    f[0][0][i] = 1;
    for (long long j = (0); j <= (n - 1); j++)
      for (long long k = (0); k <= (m - 1); k++)
        for (long long l = (0); l <= (m - 1); l++)
          if (f[j][k][l]) {
            for (long long p = (0); p <= (1); p++) {
              long long x = ch[k][p], y = ch[l][p];
              if (x != m && y != m) f[j + 1][x][y] += f[j][k][l];
            }
          }
    for (long long j = (0); j <= (m - 1); j++) ans -= f[n][i][j];
  }
  wrn(ans);
}
