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;
struct node {
  int next[2];
  int go[2];
  int suflink;
  int parent;
  int parent_char;
  bool term;
};
node t[2000];
int root = 1;
int E = 2;
int go(int v, int c);
int getSufLink(int v);
void add(const string &s) {
  int u = root;
  for (int i = 0; i < (int)s.size(); i++) {
    int c = s[i] - '0';
    if (!t[u].next[c]) {
      t[E].parent = u;
      t[E].parent_char = c;
      t[u].next[c] = E++;
    }
    u = t[u].next[c];
  }
  t[u].term = true;
}
int go(int v, int c) {
  if (!t[v].go[c]) {
    if (t[v].next[c])
      t[v].go[c] = t[v].next[c];
    else if (v == root)
      t[v].go[c] = root;
    else
      t[v].go[c] = go(getSufLink(v), c);
  }
  return t[v].go[c];
}
int getSufLink(int v) {
  if (!t[v].suflink) {
    if (v == root || t[v].parent == root)
      t[v].suflink = root;
    else {
      t[v].suflink = go(getSufLink(t[v].parent), t[v].parent_char);
    }
  }
  return t[v].suflink;
}
int n;
string s;
long long d[45][2][2000];
char a[2000][2000];
int state_s;
bool go(string a, string b) {
  int n = a.size();
  int m = b.size();
  for (int i = 0; i < n - m + 1; i++) {
    bool ok = true;
    for (int j = 0; j < m; j++) {
      if (a[i + j] != b[j]) {
        ok = false;
        break;
      }
    }
    if (ok) return true;
  }
  return false;
}
bool solve(string a, string b) {
  for (int i = 0; i < (int)a.size(); i++) {
    string r = a.substr(i, a.size() - i) + a.substr(0, i);
    if (go(r, b)) return true;
  }
  return false;
}
int stupid(int n, string s) {
  int an = 0;
  for (int i = 0; i < (1 << n); i++) {
    string cur;
    for (int j = 0; j < n; j++) {
      if (i & (1 << j))
        cur.push_back('1');
      else
        cur.push_back('0');
    }
    if (solve(cur, s)) {
      an++;
    }
  }
  return an;
}
long long solve2(string left, string right) {
  if (left.size() + right.size() > n) {
    string tmp;
    tmp.resize(n);
    for (int i = 0; i < left.size(); i++) tmp[i] = left[i];
    for (int i = right.size() - 1, j = n - 1; i >= 0; i--, j--) {
      if (tmp[j] == 0)
        tmp[j] = right[i];
      else if (tmp[j] != right[i])
        return 0;
    }
    return tmp != s;
  }
  long long d[45][E];
  memset(d, 0, sizeof(d));
  d[0][1] = 1;
  int u = root;
  for (int j = 0; j < left.size(); j++) {
    int to = go(u, left[j] - '0');
    d[j + 1][to] += d[j][u];
    u = to;
  }
  int len = (int)left.size();
  for (int j = len + 1; j <= n; j++) {
    for (int u = 1; u < E; u++) {
      int to_0 = go(u, 0);
      if (to_0 != state_s) d[j][to_0] += d[j - 1][u];
      int to_1 = go(u, 1);
      if (to_1 != state_s) d[j][to_1] += d[j - 1][u];
    }
  }
  int need = root;
  for (int j = 0; j < right.size(); j++) {
    need = go(need, right[j] - '0');
  }
  long long val = 0;
  for (int j = 1; j < E; j++) {
    if (a[j][need]) val += d[n][j];
  }
  return val;
}
int main() {
  cin >> n;
  cin >> s;
  add(s);
  for (int i = 1; i < (int)s.size(); i++) {
    add(s.substr(i, s.size() - i));
    add(s.substr(0, i));
  }
  for (int j = 1; j < E; j++) {
    int u = j;
    while (u != root) {
      a[j][u] = true;
      u = getSufLink(u);
    }
  }
  state_s = s.size() + 1;
  d[0][0][1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 2; j++) {
      for (int u = 1; u < E; u++) {
        int to_0 = go(u, 0);
        int new_j = j | (to_0 == state_s);
        d[i][new_j][to_0] += d[i - 1][j][u];
        int to_1 = go(u, 1);
        new_j = j | (to_1 == state_s);
        d[i][new_j][to_1] += d[i - 1][j][u];
      }
    }
  }
  long long an = 0;
  for (int i = 1; i < E; i++) {
    an += d[n][1][i];
  }
  vector<pair<int, int> > sex;
  for (int i = 1; i < (int)s.size(); i++) {
    long long d[45][E];
    memset(d, 0, sizeof(d));
    d[0][1] = 1;
    int u = root;
    for (int j = i; j < (int)s.size(); j++) {
      int to = go(u, s[j] - '0');
      d[j - i + 1][to] += d[j - i][u];
      u = to;
    }
    int len = (int)s.size() - i;
    for (int j = len + 1; j <= n; j++) {
      for (int u = 1; u < E; u++) {
        int to_0 = go(u, 0);
        if (to_0 != state_s) d[j][to_0] += d[j - 1][u];
        int to_1 = go(u, 1);
        if (to_1 != state_s) d[j][to_1] += d[j - 1][u];
      }
    }
    int need = root;
    for (int j = 0; j < i; j++) {
      need = go(need, s[j] - '0');
    }
    for (int j = 1; j < E; j++) {
      if (a[j][need]) an += d[n][j];
    }
  }
  for (int i = 1; i < (int)s.size(); i++) {
    string pref1 = s.substr(i, s.size() - i);
    string suf1 = s.substr(0, i);
    for (int j = i + 1; j < (int)s.size(); j++) {
      string pref2 = s.substr(j, s.size() - j);
      string suf2 = s.substr(0, j);
      if (pref1.substr(0, pref2.size()) == pref2) {
        if (suf2.substr(j - i, i) == suf1) {
          an -= solve2(pref1, suf2);
          suf1 = suf2;
        }
      }
    }
  }
  cout << an << endl;
  return 0;
}
