#include <bits/stdc++.h>
using namespace std;
const int N = 45;
vector<int> build_lps(string p) {
  int sz = p.size();
  vector<int> lps;
  lps.assign(sz, 0);
  int j = 0;
  lps[0] = 0;
  for (int i = 1; i < sz; i++) {
    while (j >= 0 && p[i] != p[j]) {
      if (j >= 1)
        j = lps[j - 1];
      else
        j = -1;
    }
    j++;
    lps[i] = j;
  }
  return lps;
}
vector<int> lps;
string s;
int m;
inline int add(int j, char ch) {
  if (j == m) j = lps[j - 1];
  while (j >= 0 && s[j] != ch) {
    if (j >= 1)
      j = lps[j - 1];
    else
      j = -1;
  }
  j++;
  return j;
}
long long dp[2][N][N][N];
long long yo(int n, int cur, int en, int got) {
  if (cur == m) got = 1;
  if (n == 0) return cur == en && got;
  long long &ret = dp[got][n][cur][en];
  if (ret != -1) return ret;
  ret = 0;
  for (char ch = '0'; ch <= '1'; ch++) {
    ret += yo(n - 1, add(cur, ch), en, got);
  }
  return ret;
}
int32_t main() {
  int n;
  cin >> n;
  cin >> s;
  m = s.size();
  lps = build_lps(s);
  long long ans = 0;
  memset(dp, -1, sizeof dp);
  for (int i = 0; i <= m; i++) ans += yo(n, i, i, 0);
  cout << ans << '\n';
  return 0;
}
