#include <bits/stdc++.h>
using namespace std;
int N, M;
string S;
int pre[45][2];
int A[45][45][2][2];
long long dp[45][45][45][45][2][2];
bool check(string& cur) {
  for (int i = 0; i + M <= cur.size(); i++)
    if (S == cur.substr(i, M)) return true;
  return false;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> N >> S;
  M = S.size();
  for (int i = 0; i <= M; i++)
    for (int j = 0; j < 2; j++) {
      string prefix = S.substr(0, i);
      prefix += (char)(j + '0');
      for (int k = min(M, (int)prefix.size()); k >= 1; k--)
        if (S.substr(0, k) == prefix.substr(prefix.size() - k, k)) {
          pre[i][j] = k;
          break;
        }
    }
  for (int i = 0; i < M; i++)
    for (int j = i; j <= M; j++)
      for (int c = 0; c < 2; c++) {
        string cur = S.substr(i, j - i);
        cur += (char)(c + '0');
        A[i][j][c][0] = -1;
        A[i][j][c][1] = -1;
        for (int k = 0; k + cur.size() <= M; k++)
          if (S.substr(k, cur.size()) == cur) {
            A[i][j][c][0] = k;
            A[i][j][c][1] = k + cur.size();
            break;
          }
      }
  dp[0][0][0][0][0][0] = 1;
  for (int i = 0; i < N; i++)
    for (int a = 0; a < M; a++)
      for (int b = a; b <= M; b++)
        for (int done = 0; done < 2; done++)
          for (int j = 0; j <= M; j++)
            for (int c = 0; c < 2; c++) {
              int l = done ? a : A[a][b][c][0];
              int r = done ? b : A[a][b][c][1];
              int flag = done;
              if (l == -1) {
                l = a, r = b;
                flag = true;
              }
              if (pre[j][c] != M)
                dp[i + 1][l][r][pre[j][c]][0][flag] += dp[i][a][b][j][0][done];
              else
                dp[i + 1][l][r][pre[j][c]][1][flag] += dp[i][a][b][j][0][done];
              dp[i + 1][l][r][pre[j][c]][1][flag] += dp[i][a][b][j][1][done];
            }
  long long ans = 0;
  for (int a = 0; a < M; a++)
    for (int b = a; b <= M; b++)
      for (int done = 0; done < 2; done++)
        for (int j = 0; j <= M; j++) {
          if (dp[N][a][b][j][0][done] > 0) {
            string cur = S.substr(0, j) + S.substr(a, b - a);
            if (check(cur)) ans += dp[N][a][b][j][0][done];
          }
          ans += dp[N][a][b][j][1][done];
        }
  cout << ans << "\n";
  return 0;
}
