#include <bits/stdc++.h>
using namespace std;
char s[41];
int n, m, fail[41], mem[41][2];
long long F[41][41], G[41][41];
vector<int> pre[41][2];
inline int getnext(int now, char ch) {
  int &ret = mem[now][ch - '0'];
  if (~ret) return ret;
  if (now == m) now = fail[now - 1];
  while (s[now] != ch) {
    if (!now) return ret = 0;
    now = fail[now - 1];
  }
  return ret = now + 1;
}
long long f(int x, int a) {
  if (!x) return a == m;
  long long &ret = F[x][a];
  if (~ret) return ret;
  ret = 0;
  for (int i = 0; i <= 1; ++i)
    for (int j = 0; j < (int)pre[a][i].size(); ++j) {
      int nxt = pre[a][i][j];
      ret += f(x - 1, nxt);
    }
  return ret;
}
long long g(int x, int a) {
  if (!x) return a == m;
  long long &ret = G[x][a];
  if (~ret) return ret;
  ret = 0;
  for (char i = '0'; i <= '1'; ++i) {
    int nxt = getnext(a, i);
    if (x - 1 > 0 && nxt == m) continue;
    ret += g(x - 1, nxt);
  }
  return ret;
}
int main() {
  memset(mem, -1, sizeof mem);
  memset(F, -1, sizeof F);
  memset(G, -1, sizeof G);
  scanf("%d%s", &n, s);
  m = strlen(s);
  for (int i = 1; i < m; ++i) {
    fail[i] = fail[i - 1];
    while (s[fail[i]] != s[i]) {
      if (!fail[i]) break;
      fail[i] = fail[fail[i] - 1];
    }
    if (s[fail[i]] == s[i]) ++fail[i];
  }
  for (int i = 0; i <= m; ++i)
    for (int j = 0; j <= 1; ++j) pre[getnext(i, j + '0')][j].push_back(i);
  long long res = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j <= m; ++j) res += g(n - i, j) * f(i, j);
  cout << res << endl;
  return 0;
}
