#include <bits/stdc++.h>
using ul = std::uint32_t;
using ull = std::uint64_t;
using li = std::int32_t;
using ll = std::int64_t;
using vb = std::vector<bool>;
using vul = std::vector<ul>;
using vvul = std::vector<vul>;
using vull = std::vector<ull>;
using vvull = std::vector<vull>;
using vvvull = std::vector<vvull>;
using vvvvull = std::vector<vvvull>;
vb s;
ul n;
vvul kmp(41, vul(2, 0));
vvvvull f(41, vvvull(41, vvull(41, vull(41, 0))));
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cin >> n;
  while (true) {
    char ch;
    if (!(std::cin >> ch)) {
      break;
    }
    s.push_back(ch == '1');
  }
  vul kmptemp(s.size() + 1, 0);
  for (ul i = 1, j = 0; i != s.size();) {
    while (s[i] != s[j] && j) {
      j = kmptemp[j];
    }
    if (s[i] == s[j]) {
      ++i;
      ++j;
    } else {
      ++i;
    }
    kmptemp[i] = j;
  }
  for (ul i = 0; i != s.size(); ++i) {
    for (bool c : {false, true}) {
      if (c == s[i]) {
        kmp[i][c] = i + 1;
      } else {
        kmp[i][c] = kmp[kmptemp[i]][c];
      }
    }
  }
  for (bool c : {false, true}) {
    kmp[s.size()][c] = s.size();
  }
  for (ul c = 0; c <= s.size(); ++c) {
    f[0][0][c][c] = 1;
  }
  for (ul a = 0; a != n; ++a) {
    for (ul b = 0; b <= s.size(); ++b) {
      for (ul c = 0; c <= s.size(); ++c) {
        for (ul d = 0; d <= s.size(); ++d) {
          if (!f[a][b][c][d]) {
            continue;
          }
          for (bool ch : {false, true}) {
            f[a + 1][kmp[b][ch]][c][kmp[d][ch]] += f[a][b][c][d];
          }
        }
      }
    }
  }
  ull ans = 0;
  for (ul i = 0; i <= s.size(); ++i) {
    ans += f[n][i][i][s.size()];
  }
  std::cout << ans << std::endl;
  return 0;
}
