#include <bits/stdc++.h>
using namespace std;
int n, m;
long long unit, top;
void put(long long x, int sz = n) {
  for (int i = 0; i < sz; i++) printf("%d", (x >> i) & 1);
  puts("");
}
char tmp_[55];
long long ans[40 * (1 << 18) + 10];
void brute_solve() {
  long long now = 0;
  for (int i = 0; i < m; i++)
    if (tmp_[i] == '1') now += 1ll << i;
  int e = 0;
  for (; now < top; now += unit) {
    for (int i = 0; i < n; i++)
      ans[++e] = (now >> i) + ((now & ((1ll << i) - 1)) << (n - i));
  }
  sort(ans + 1, ans + e + 1);
  int rlt = 0;
  for (int i = 1; i <= e; i++)
    if (i == 1 || ans[i] > ans[i - 1]) rlt++;
  printf("%d\n", rlt);
}
int pat;
bool same(int sz, int x, int y) {
  int t = (1 << sz) - 1;
  return (x & t) == (y & t);
}
bool inside(int n, int now) {
  if (m > n) return 0;
  for (int d = 0; d <= n - m; d++)
    if (same(m, now >> d, pat)) return 1;
  return 0;
}
bool same(int sz, long long x, long long y) {
  long long t = (1ll << sz) - 1;
  return (x & t) == (y & t);
}
bool inside(int n, long long now) {
  if (m > n) return 0;
  for (int d = 0; d <= n - m; d++)
    if (same(m, now >> d, 1ll * pat)) return 1;
  return 0;
}
bool check(int i, int j) {
  if (i + j < m) return 0;
  long long t = (pat & ((1 << j) - 1)) + (((1ll * pat) >> (m - i)) << j);
  return inside(i + j, t);
}
int a[33][33], b[33][33];
void prep(int n, int a[][33]) {
  pat = 0;
  for (int i = 0; i < m; i++)
    if (tmp_[i] == '1') pat += 1 << i;
  int tic = 1 << n;
  for (int now = 0; now < tic; now++) {
    if (inside(n, now))
      a[m][m]++;
    else {
      int A, B;
      for (int i = min(n, m - 1); i >= 0; i--) {
        if (same(i, now, pat >> (m - i))) {
          A = i;
          break;
        }
      }
      for (int i = min(n, m - 1); i >= 0; i--) {
        if (same(i, pat, now >> (n - i))) {
          B = i;
          break;
        }
      }
      a[A][B]++;
    }
  }
}
void tight_solve() {
  int n1 = n / 2, n2 = n - n1;
  prep(n1, a);
  prep(n2, b);
  long long ans = 0;
  ans += 1ll * a[m][m] * (1 << n2);
  ans += 1ll * b[m][m] * (1 << n1);
  ans -= 1ll * a[m][m] * b[m][m];
  for (int i = 0; i < m; i++)
    for (int j = 0; j < m; j++)
      for (int ii = 0; ii < m; ii++)
        for (int jj = 0; jj < m; jj++) {
          if (check(i, jj) || check(ii, j)) {
            ans += 1ll * a[i][j] * b[ii][jj];
          }
        }
  printf("%I64d\n", ans);
}
int main() {
  scanf("%d", &n);
  scanf("%s", tmp_);
  m = strlen(tmp_);
  unit = 1ll << m;
  top = 1ll << n;
  if (n > 2 && m < (n / 2) + 2)
    tight_solve();
  else
    brute_solve();
  return 0;
}
