#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long linf = 1e18;
const int N = 40 + 10;
const double eps = 1e-5;
const int mo = 1e9 + 7;
int n, m;
long long bin[N];
string s;
struct node {
  int x;
  int a, b;
};
long long len[N][N][N][N];
long long ans;
bool check(int x, int y) {
  if (x < y) {
    if (y - x >= m) return 1;
    int l = m - y + x;
    for (int i = 1; i <= l; i++) {
      if (s[i - 1] != s[m - l + 1 + i - 2]) return 0;
    }
    return 1;
  } else {
    int cutlen = (x + m - 1) - n;
    if (cutlen < y) return 1;
    int l = cutlen - y + 1;
    for (int i = 1; i <= l; i++) {
      if (s[i - 1] != s[m - l + 1 + i - 2]) return 0;
    }
    return 1;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> s;
  bin[0] = 1;
  for (int i = 1; i <= n; i++) bin[i] = bin[i - 1] * 2;
  m = s.size();
  node t, u;
  t.x = 1;
  for (int i = 1; i <= n; i++) {
    t.a = t.b = i;
    ++len[t.x][t.a][t.b][m];
  }
  for (int tot = 2; tot <= n; tot++) {
    for (int i = 1; i <= n; i++) {
      u.x = tot, u.b = i;
      for (int j = 1; j <= i - 1; j++)
        if (check(j, i)) {
          t.x = tot - 1, t.b = j;
          for (int k = 1; k <= j; k++)
            if (check(i, k)) {
              t.a = k;
              u.a = k;
              int d = 0, cutlen = 0;
              if (j + m - 1 <= n) {
                cutlen = i + m - 1 - n;
                if (cutlen < k)
                  d = min(m, i - j);
                else
                  d = min(m, i - j) - (cutlen - k + 1);
              } else {
                cutlen = i - j;
                int start = (j + m - 1 - n) + 1;
                if (start >= k)
                  d = 0;
                else {
                  if (start + cutlen - 1 >= k)
                    d = k - start;
                  else
                    d = i - j;
                }
              }
              for (int k = 1; k <= n - d; k++)
                len[u.x][u.a][u.b][k + d] += len[t.x][t.a][t.b][k];
            }
        }
    }
  }
  for (int i = 1; i <= n; i++) {
    long long cnt;
    long long res = 0;
    int x = i;
    for (int a = 1; a <= n; a++)
      for (int b = a; b <= n; b++)
        for (int l = 1; l <= n; l++) {
          cnt = len[x][a][b][l];
          res += cnt * bin[n - l];
        }
    if (i % 2)
      ans += res;
    else
      ans -= res;
  }
  cout << ans << endl;
  return 0;
}
