You are given a binary string s.

Find the number of distinct cyclical binary strings of length n which contain s as a substring.

The cyclical string t contains s as a substring if there is some cyclical shift of string t, such that s is a substring of this cyclical shift of t.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.

Input

The first line contains a single integer n (1 ≤ n ≤ 40) — the length of the target string t.

The next line contains the string s (1 ≤ |s| ≤ n) — the string which must be a substring of cyclical string t. String s contains only characters '0' and '1'.

Output

Print the only integer — the number of distinct cyclical binary strings t, which contain s as a substring.

Examples

Input

2
0


Output

3

Input

4
1010


Output

2

Input

20
10101010101010


Output

962

Note

In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
namespace Mymath {
long long qp(long long x, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return ans;
}
long long inv(long long x, long long mod) { return qp(x, mod - 2, mod); }
long long C(long long N, long long K, long long fact[], long long mod) {
  return fact[N] * inv(fact[K], mod) % mod * inv(fact[N - K], mod) % mod;
}
template <typename Tp>
Tp gcd(Tp A, Tp B) {
  if (B == 0) return A;
  return gcd(B, A % B);
}
template <typename Tp>
Tp lcm(Tp A, Tp B) {
  return A * B / gcd(A, B);
}
};  // namespace Mymath
namespace fwt {
using namespace Mymath;
void FWT(int a[], int n, long long mod) {
  for (int d = 1; d < n; d <<= 1)
    for (int m = d << 1, i = 0; i < n; i += m)
      for (int j = 0; j < d; j++) {
        int x = a[i + j], y = a[i + j + d];
        a[i + j] = (x + y) % mod, a[i + j + d] = (x - y + mod) % mod;
      }
}
void UFWT(int a[], int n, long long mod) {
  long long rev = inv(2, mod);
  for (int d = 1; d < n; d <<= 1)
    for (int m = d << 1, i = 0; i < n; i += m)
      for (int j = 0; j < d; j++) {
        int x = a[i + j], y = a[i + j + d];
        a[i + j] = 1LL * (x + y) * rev % mod,
              a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;
      }
}
void solve(int a[], int b[], int n, long long mod) {
  FWT(a, n, mod);
  FWT(b, n, mod);
  for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * b[i] % mod;
  UFWT(a, n, mod);
}
};  // namespace fwt
namespace Maxflow {
const int Maxn = 1005;
struct edge {
  int to, rev, cap;
  edge(int _to, int _rev, int _cap) { to = _to, rev = _rev, cap = _cap; }
};
int src = 1002, snk = 1003;
vector<edge> G[Maxn];
int dist[Maxn], seen[Maxn];
int n;
void Clear() {
  for (int i = 0; i < Maxn; i++) G[i].clear();
}
void bfs(int s) {
  for (int i = 0; i < Maxn; i++) dist[i] = -1;
  dist[s] = 0;
  queue<int> Q;
  Q.push(s);
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int i = 0; i < G[x].size(); i++) {
      edge &e = G[x][i];
      if (e.cap && dist[e.to] == -1) {
        dist[e.to] = dist[x] + 1;
        Q.push(e.to);
      }
    }
  }
}
int dfs(int now, int dest, int fl) {
  if (now == dest) return fl;
  for (int &i = seen[now]; i < G[now].size(); i++) {
    edge &ed = G[now][i];
    if (ed.cap && dist[ed.to] == dist[now] + 1) {
      int f = dfs(ed.to, dest, min(fl, ed.cap));
      if (f) {
        ed.cap -= f;
        G[ed.to][ed.rev].cap += f;
        return f;
      }
    }
  }
  return 0;
}
int dinic(int s = src, int t = snk) {
  int ret = 0;
  while (1) {
    memset(seen, 0, sizeof(seen));
    bfs(s);
    if (dist[t] == -1) return ret;
    int f = dfs(s, t, 2147483647);
    while (f) {
      ret += f;
      f = dfs(s, t, 2147483647);
    }
  }
}
};  // namespace Maxflow
namespace Geometry {
struct iP {
  long long x, y;
  iP(long long _x, long long _y) { x = _x, y = _y; }
  iP() { x = y = 0; }
  iP operator+(iP p) { return iP(x + p.x, y + p.y); }
  iP operator-(iP p) { return iP(x - p.x, y - p.y); }
  iP operator*(long long k) { return iP(x * k, y * k); }
  long long det(iP p) { return x * p.y - y * p.x; }
  long long dot(iP p) { return x * p.x + y * p.y; }
  long long dist() { return x * x + y * y; }
  bool operator<(const iP &p) const {
    if (x != p.x) return x < p.x;
    return y < p.y;
  }
};
struct dP {
  double x, y;
  dP(double _x, double _y) { x = _x, y = _y; }
  dP() { x = y = 0.0; }
  dP operator+(dP p) { return dP(x + p.x, y + p.y); }
  dP operator-(dP p) { return dP(x - p.x, y - p.y); }
  dP operator*(double k) { return dP(x * k, y * k); }
  double det(dP p) { return x * p.y - y * p.x; }
  double dot(dP p) { return x * p.x + y * p.y; }
  double dist() { return x * x + y * y; }
  bool operator<(const dP &p) const {
    if (x != p.x) return x < p.x;
    return y < p.y;
  }
};
vector<iP> convex_hull(iP X[], int l) {
  vector<iP> ret;
  sort(X + 1, X + 1 + l);
  ret.push_back(X[1]);
  for (int i = 2; i <= l; i++) {
    while (ret.size() >= 2 &&
           (ret[ret.size() - 2] - X[i]).det(ret[ret.size() - 1] - X[i]) >= 0) {
      ret.pop_back();
    }
    ret.push_back(X[i]);
  }
  int rs = ret.size() + 1;
  for (int i = l - 1; i >= 1; i--) {
    while (ret.size() >= rs &&
           (ret[ret.size() - 2] - X[i]).det(ret[ret.size() - 1] - X[i]) >= 0) {
      ret.pop_back();
    }
    ret.push_back(X[i]);
  }
  return ret;
}
};  // namespace Geometry
const int Maxn = 85;
int n;
string s;
int nxt[Maxn][2];
long long dp[Maxn][Maxn][Maxn][2];
int main() {
  n = read();
  cin >> s;
  for (int i = 0; i <= s.size(); i++) {
    for (int j = 0; j < 2; j++) {
      string t = s.substr(0, i) + (char)(j + '0');
      for (int k = 0; k < t.size(); k++) {
        bool flag = true;
        for (int l = k; l < t.size(); l++) {
          if (l - k >= s.size() || t[l] != s[l - k]) {
            flag = false;
            break;
          }
        }
        if (flag) {
          nxt[i][j] = t.size() - k;
          break;
        }
      }
    }
  }
  long long ans = 0;
  for (int md = 0; md <= s.size(); md++) {
    memset(dp, 0, sizeof(dp));
    dp[0][0][md][md == s.size()] = 1;
    for (int j = 0; j < n; j++) {
      for (int s1 = 0; s1 <= s.size(); s1++) {
        for (int s2 = 0; s2 <= s.size(); s2++) {
          for (int f = 0; f < 2; f++) {
            for (int nx = 0; nx < 2; nx++) {
              dp[j + 1][nxt[s1][nx]][nxt[s2][nx]]
                [f | (nxt[s1][nx] == s.size()) | (nxt[s2][nx] == s.size())] +=
                  dp[j][s1][s2][f];
            }
          }
        }
      }
    }
    for (int s2 = 0; s2 <= s.size(); s2++) {
      ans += dp[n][md][s2][1];
    }
  }
  printf("%I64d\n", ans);
  return ~~(0 ^ 0 ^ 0);
}
