#include <bits/stdc++.h>
using namespace std;
struct node {
  int next[2];
  int go[2];
  int suflink;
  int parent;
  int parent_char;
  bool term;
};
node t[2000];
int root = 1;
int E = 2;
int go(int v, int c);
int getSufLink(int v);
void add(const string &s) {
  int u = root;
  for (int i = 0; i < (int)s.size(); i++) {
    int c = s[i] - '0';
    if (!t[u].next[c]) {
      t[E].parent = u;
      t[E].parent_char = c;
      t[u].next[c] = E++;
    }
    u = t[u].next[c];
  }
  t[u].term = true;
}
int go(int v, int c) {
  if (!t[v].go[c]) {
    if (t[v].next[c])
      t[v].go[c] = t[v].next[c];
    else if (v == root)
      t[v].go[c] = root;
    else
      t[v].go[c] = go(getSufLink(v), c);
  }
  return t[v].go[c];
}
int getSufLink(int v) {
  if (!t[v].suflink) {
    if (v == root || t[v].parent == root)
      t[v].suflink = root;
    else {
      t[v].suflink = go(getSufLink(t[v].parent), t[v].parent_char);
    }
  }
  return t[v].suflink;
}
int n;
string s;
long long d[45][2][2000];
char a[2000][2000];
int state_s;
bool go(string a, string b) {
  int n = a.size();
  int m = b.size();
  for (int i = 0; i < n - m + 1; i++) {
    bool ok = true;
    for (int j = 0; j < m; j++) {
      if (a[i + j] != b[j]) {
        ok = false;
        break;
      }
    }
    if (ok) return true;
  }
  return false;
}
bool solve(string a, string b) {
  for (int i = 0; i < (int)a.size(); i++) {
    string r = a.substr(i, a.size() - i) + a.substr(0, i);
    if (go(r, b)) return true;
  }
  return false;
}
int stupid(int n, string s) {
  int an = 0;
  for (int i = 0; i < (1 << n); i++) {
    string cur;
    for (int j = 0; j < n; j++) {
      if (i & (1 << j))
        cur.push_back('1');
      else
        cur.push_back('0');
    }
    if (solve(cur, s)) {
      an++;
    }
  }
  return an;
}
long long solve2(string left, string right) {
  if (left.size() + right.size() > n) {
    string tmp;
    tmp.resize(n);
    for (int i = 0; i < left.size(); i++) tmp[i] = left[i];
    for (int i = right.size() - 1, j = n - 1; i >= 0; i--, j--) {
      if (tmp[j] == 0)
        tmp[j] = right[i];
      else if (tmp[j] != right[i])
        return 0;
    }
    return tmp != s;
  }
  long long d[45][E];
  memset(d, 0, sizeof(d));
  d[0][1] = 1;
  int u = root;
  for (int j = 0; j < left.size(); j++) {
    int to = go(u, left[j] - '0');
    d[j + 1][to] += d[j][u];
    u = to;
  }
  int len = (int)left.size();
  for (int j = len + 1; j <= n; j++) {
    for (int u = 1; u < E; u++) {
      int to_0 = go(u, 0);
      if (to_0 != state_s) d[j][to_0] += d[j - 1][u];
      int to_1 = go(u, 1);
      if (to_1 != state_s) d[j][to_1] += d[j - 1][u];
    }
  }
  int need = root;
  for (int j = 0; j < right.size(); j++) {
    need = go(need, right[j] - '0');
  }
  long long val = 0;
  for (int j = 1; j < E; j++) {
    if (a[j][need]) val += d[n][j];
  }
  return val;
}
int main() {
  cin >> n;
  cin >> s;
  add(s);
  for (int i = 1; i < (int)s.size(); i++) {
    add(s.substr(i, s.size() - i));
    add(s.substr(0, i));
  }
  for (int j = 1; j < E; j++) {
    int u = j;
    while (u != root) {
      a[j][u] = true;
      u = getSufLink(u);
    }
  }
  state_s = s.size() + 1;
  d[0][0][1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 2; j++) {
      for (int u = 1; u < E; u++) {
        int to_0 = go(u, 0);
        int new_j = j | (to_0 == state_s);
        d[i][new_j][to_0] += d[i - 1][j][u];
        int to_1 = go(u, 1);
        new_j = j | (to_1 == state_s);
        d[i][new_j][to_1] += d[i - 1][j][u];
      }
    }
  }
  long long an = 0;
  for (int i = 1; i < E; i++) {
    an += d[n][1][i];
  }
  vector<pair<int, int> > sex;
  for (int i = 1; i < (int)s.size(); i++) {
    long long d[45][E];
    memset(d, 0, sizeof(d));
    d[0][1] = 1;
    int u = root;
    for (int j = i; j < (int)s.size(); j++) {
      int to = go(u, s[j] - '0');
      d[j - i + 1][to] += d[j - i][u];
      u = to;
    }
    int len = (int)s.size() - i;
    for (int j = len + 1; j <= n; j++) {
      for (int u = 1; u < E; u++) {
        int to_0 = go(u, 0);
        if (to_0 != state_s) d[j][to_0] += d[j - 1][u];
        int to_1 = go(u, 1);
        if (to_1 != state_s) d[j][to_1] += d[j - 1][u];
      }
    }
    int need = root;
    for (int j = 0; j < i; j++) {
      need = go(need, s[j] - '0');
    }
    for (int j = 1; j < E; j++) {
      if (a[j][need]) an += d[n][j];
    }
  }
  for (int i = 1; i < (int)s.size(); i++) {
    string pref1 = s.substr(i, s.size() - i);
    string suf1 = s.substr(0, i);
    for (int j = i + 1; j < (int)s.size(); j++) {
      string pref2 = s.substr(j, s.size() - j);
      string suf2 = s.substr(0, j);
      if (pref1.substr(0, pref2.size()) == pref2) {
        if (suf2.substr(j - i, i) == suf1) {
          an -= solve2(pref1, suf2);
          suf1 = suf2;
        }
      }
    }
  }
  cout << an << endl;
  return 0;
}
