#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 40;
int n;
char s[MAXN + 1];
int slen;
long long dp[MAXN][MAXN][MAXN + 1];
long long sum[MAXN + 1];
bool can[MAXN][MAXN];
long long solve() {
  for (int i = (0); i < (n); ++i) can[i][i] = true;
  for (int i = (0); i < (n); ++i)
    for (int j = (i + 1); j < (n); ++j) {
      can[i][j] = true;
      for (int k = (0); k < (slen); ++k)
        if (i + k >= j && s[k] != s[i + k - j] ||
            j + k >= i + n && s[k] != s[j + k - i - n])
          can[i][j] = false;
      can[j][i] = can[i][j];
    }
  memset(dp, 0, sizeof(dp));
  for (int i = (0); i < (n); ++i) dp[i][i][1] = 1;
  for (int fst = (0); fst < (n); ++fst)
    for (int lst = (fst); lst < (n); ++lst)
      for (int i = (1); i <= (lst - fst + 1); ++i)
        if (dp[fst][lst][i] != 0) {
          for (int nxt = (lst + 1); nxt < (n); ++nxt)
            if (can[fst][nxt] && can[lst][nxt]) {
              int nfree = max(0, nxt - lst - slen);
              dp[fst][nxt][i + 1] += dp[fst][lst][i] << nfree;
            }
        }
  memset(sum, 0, sizeof(sum));
  for (int fst = (0); fst < (n); ++fst)
    for (int lst = (fst); lst < (n); ++lst)
      for (int i = (1); i <= (lst - fst + 1); ++i)
        if (dp[fst][lst][i] != 0) {
          int nfree = max(0, fst + n - lst - slen);
          sum[i] += dp[fst][lst][i] << nfree;
        }
  sum[0] = 1LL << n;
  long long none = 0;
  for (int i = (0); i <= (n); ++i) {
    long long cur = sum[i];
    if (i % 2 == 0)
      none += cur;
    else
      none -= cur;
  }
  return (1LL << n) - none;
}
void run() {
  scanf("%d", &n);
  scanf("%s", s);
  slen = strlen(s);
  printf("%lld\n", solve());
}
int main() {
  run();
  return 0;
}
