#include <bits/stdc++.h>
using namespace std;
long long ans;
int n, m;
string s;
map<string, int> Id;
set<string> P;
vector<string> S;
long long f[41][1610][41][2];
void work(int len, int A, int B, int O, char c) {
  string str = S[A] + c;
  int toA = A;
  if (str.length() == len + 1 && Id.count(str)) toA = Id[str];
  str = S[B] + c;
  while (P.find(str) == P.end()) str = str.substr(1, str.length() - 1);
  int toB = str.length();
  int toO = O;
  if (toB == m) toO = 1;
  f[len + 1][toA][toB][toO] += f[len][A][B][O];
  return;
}
void solve(int len, int A, int B, int O) {
  if (!f[len][A][B][O]) return;
  if (len == n) {
    if (O)
      ans += f[len][A][B][O];
    else {
      string str = S[B] + S[A];
      if (str.find(s) != string::npos) ans += f[len][A][B][O];
    }
    return;
  }
  work(len, A, B, O, '0');
  work(len, A, B, O, '1');
  return;
}
void Ins(string str) {
  if (Id.count(str)) return;
  Id[str] = S.size();
  S.push_back(str);
  return;
}
int main() {
  cin >> n >> s;
  m = s.length();
  string str = "";
  Ins(str);
  P.insert(str);
  for (int i = 0; i < m; i++) {
    str += s[i];
    P.insert(str);
  }
  for (int i = 0; i < m; i++) {
    str = "";
    for (int j = i; j < m; j++) {
      str += s[j];
      Ins(str);
    }
  }
  int N = S.size();
  f[0][0][0][0] = 1;
  for (int len = 0; len <= n; len++)
    for (int A = 0; A < N; A++)
      for (int B = 0; B <= m; B++)
        for (int O = 0; O < 2; O++) solve(len, A, B, O);
  printf("%lld\n", ans);
  return 0;
}
