#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
int n, m, i, j, k, s, fa[45], ch[45][2];
long long dp[45][45][45];
string st;
void build(string st) {
  int i, j;
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    ch[i][st[i - 1] & 1] = i + 1;
  }
  queue<int> q;
  for (((i)) = (0); ((i)) <= (((int)(2)) - 1); ((i))++)
    if (!ch[1][i])
      ch[1][i] = 1;
    else {
      fa[ch[1][i]] = 1;
      q.push(ch[1][i]);
    }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (((i)) = (0); ((i)) <= (((int)(2)) - 1); ((i))++) {
      if (ch[x][i]) {
        int y = ch[x][i];
        fa[y] = ch[fa[x]][i];
        q.push(y);
      } else
        ch[x][i] = ch[fa[x]][i];
    }
  }
}
int main() {
  cin >> m >> st;
  n = st.size();
  build(st);
  long long ans = (1ll << m);
  for (((s)) = (1); ((s)) <= ((n)); ((s))++) {
    memset(dp, 0, sizeof(dp));
    dp[0][1][s] = 1;
    for (((i)) = (1); ((i)) <= ((m)); ((i))++) {
      for (((j)) = (1); ((j)) <= ((n)); ((j))++)
        for (((k)) = (1); ((k)) <= ((n)); ((k))++)
          if (dp[i - 1][j][k]) {
            int tj = ch[j][0], tk = ch[k][0];
            dp[i][tj][tk] += dp[i - 1][j][k];
            tj = ch[j][1];
            tk = ch[k][1];
            dp[i][tj][tk] += dp[i - 1][j][k];
          }
    }
    for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
      ans -= dp[m][s][i];
    }
  }
  cout << ans << endl;
  return 0;
}
