#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, m, Next[45];
int st[45][2];
char s[45];
void get_next() {
  memset(Next, -1, sizeof(Next));
  int i, j;
  j = Next[0] = -1, i = 0;
  while (i < m) {
    if (j < 0 || s[j] == s[i]) {
      i++, j++, Next[i] = j;
    } else
      j = Next[j];
  }
}
struct Mat {
  long long a[45][45];
  Mat operator+(const Mat &_) const {
    Mat tmp;
    memset(tmp.a, 0, sizeof(tmp.a));
    for (int i = 0; i < 45; i++) {
      for (int j = 0; j < 45; j++) {
        tmp.a[i][j] = a[i][j] + _.a[i][j];
      }
    }
    return tmp;
  }
  Mat operator*(const Mat &_) const {
    Mat tmp;
    memset(tmp.a, 0, sizeof(tmp.a));
    for (int l = 0; l < 45; l++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          tmp.a[i][j] += a[i][l] * _.a[l][j];
        }
      }
    }
    return tmp;
  }
  void print() {
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        cout << a[i][j] << " ";
      }
      cout << endl;
    }
  }
} mat;
Mat qpow(Mat a, int n) {
  if (n == 1) return a;
  Mat ans = qpow(a, n >> 1);
  ans = ans * ans;
  if (n & 1) ans = ans * a;
  return ans;
}
void get_st() {
  for (int i = 0; i < m; i++) s[i] -= '0';
  st[0][s[0]] = 1;
  st[0][s[0] ^ 1] = 0;
  for (int i = 0; i < m - 1; i++) {
    int bit = s[i + 1];
    st[i + 1][bit] = i + 2;
    st[i + 1][bit ^ 1] = st[Next[i + 1]][bit ^ 1];
  }
  memset(mat.a, 0, sizeof(mat.a));
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++)
      if (st[i][j] != m) {
        mat.a[i][st[i][j]]++;
      }
  }
}
void solve() {
  Mat tmp = qpow(mat, n);
  long long ans = 0;
  for (int i = 0; i < m; i++) ans += tmp.a[i][i];
  cout << (1LL << n) - ans << endl;
}
int main() {
  while (cin >> n) {
    cin >> s;
    m = strlen(s);
    get_next();
    get_st();
    solve();
  }
  return 0;
}
