#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
long long dp[44][2][44][1611];
set<string> prefix_set;
map<string, int> substr_to_id;
vector<string> id_to_substr;
void trans(int t_len, int has, int prefix_id, int substr_id, char ch) {
  string new_suf = id_to_substr[prefix_id] + ch;
  while (!prefix_set.count(new_suf)) {
    new_suf = new_suf.substr(1);
  }
  int next_prefix_id = substr_to_id[new_suf];
  int next_has = has;
  if (has == 0 && new_suf == s) {
    next_has = 1;
  }
  const string& old_pref = id_to_substr[substr_id];
  int next_substr_id = substr_id;
  if (old_pref.size() == t_len && t_len <= m) {
    string new_pref = old_pref + ch;
    if (substr_to_id.count(new_pref)) {
      next_substr_id = substr_to_id[new_pref];
    }
  }
  dp[t_len + 1][next_has][next_prefix_id][next_substr_id] +=
      dp[t_len][has][prefix_id][substr_id];
}
int main() {
  cin >> n >> s;
  m = s.size();
  for (int i = 0; i < m; ++i) {
    for (int len = 0; i + len <= m; ++len) {
      string sub = s.substr(i, len);
      if (substr_to_id.count(sub)) continue;
      substr_to_id[sub] = id_to_substr.size();
      id_to_substr.push_back(sub);
      if (i == 0) {
        prefix_set.insert(sub);
      }
    }
  }
  long long ret = 0;
  dp[0][0][0][0] = 1;
  for (int t_len = 0; t_len <= n; ++t_len) {
    for (int has = 0; has <= 1; ++has) {
      for (int prefix_id = 0; prefix_id < prefix_set.size(); ++prefix_id) {
        for (int substr_id = 0; substr_id < id_to_substr.size(); ++substr_id) {
          long long cur_stat = dp[t_len][has][prefix_id][substr_id];
          if (!cur_stat) continue;
          if (t_len == n &&
              ((has == 1) ||
               (id_to_substr[prefix_id] + id_to_substr[substr_id]).find(s) !=
                   std::string::npos)) {
            ret += cur_stat;
          }
          trans(t_len, has, prefix_id, substr_id, '0');
          trans(t_len, has, prefix_id, substr_id, '1');
        }
      }
    }
  }
  cout << ret << endl;
}
