#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct State {
  int bk;
  string fr;
  int pos;
  int cnt;
};
bool operator<(State lhs, State rhs) {
  if (lhs.bk != rhs.bk) return lhs.bk < rhs.bk;
  if (lhs.fr != rhs.fr) return lhs.fr < rhs.fr;
  if (lhs.pos != rhs.pos) return lhs.pos < rhs.pos;
  if (lhs.cnt != rhs.cnt) return lhs.cnt < rhs.cnt;
  return false;
}
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> jump(s.size() + 1, 0);
  for (int i = 0; i <= s.size(); i++) {
    int to = 0;
    for (int j = 0; j < i; j++) {
      bool ok = true;
      for (int k = 0; k < j; k++) {
        ok &= (s[k] == s[i - j + k]);
      }
      if (i != s.size()) ok &= (s[j] != s[i]);
      if (ok) to = j + 1 - (int)(i == s.size());
    }
    jump[i] = to;
  }
  set<string> subs;
  for (int i = 0; i < s.size(); i++) {
    for (int j = i + 1; j <= s.size(); j++) {
      string ss;
      for (int k = i; k < j; k++) {
        ss += s[k];
      }
      subs.insert(ss);
    }
  }
  set<string> lasts;
  string ss;
  for (int i = s.size() - 1; i >= 0; i--) {
    ss = s[i] + ss;
    lasts.insert(ss);
  }
  map<State, ll> dp;
  dp[State{-1, "", 0, 0}] = 1;
  for (int i = 0; i < n; i++) {
    map<State, ll> next;
    for (auto &e : dp) {
      int bk = e.first.bk;
      string str = e.first.fr;
      int pos = e.first.pos;
      int cnt = e.first.cnt;
      if (str != "@") {
        str += s[pos];
        if (subs.count(str)) {
          if (lasts.count(str)) {
            bk = i;
          }
        } else {
          str = "@";
        }
      }
      if (++pos == s.size()) {
        pos = jump[pos];
        cnt = true;
      }
      next[State{bk, str, pos, cnt}] += e.second;
      bk = e.first.bk;
      str = e.first.fr;
      pos = e.first.pos;
      cnt = e.first.cnt;
      if (str != "@") {
        str += (s[pos] == '0' ? "1" : "0");
        if (subs.count(str)) {
          if (lasts.count(str)) {
            bk = i;
          }
        } else {
          str = "@";
        }
      }
      pos = jump[pos];
      next[State{bk, str, pos, cnt}] += e.second;
    }
    dp = next;
  }
  ll res = 0;
  for (auto &e : dp) {
    int bk = e.first.bk;
    string strs = e.first.fr;
    int pos = e.first.pos;
    int cnt = e.first.cnt;
    string str;
    for (int i = 0; i < e.first.pos; i++) {
      str += s[i];
    }
    for (int i = s.size() - e.first.bk - 1; i < s.size(); i++) {
      str += s[i];
    }
    for (int i = 0; i <= (int)str.size() - (int)s.size(); i++) {
      if (s == str.substr(i, s.size())) {
        cnt = true;
      }
    }
    if (cnt >= 1) {
      res += e.second;
    }
  }
  cout << res << endl;
  return 0;
}
