#include <bits/stdc++.h>   using namespace std;   using ll = long long;   struct State {     int bk;     string fr;     int pos;     int cnt;   };   bool operator<(State lhs, State rhs) {     if (lhs.bk != rhs.bk) return lhs.bk < rhs.bk;     if (lhs.fr != rhs.fr) return lhs.fr < rhs.fr;     if (lhs.pos != rhs.pos) return lhs.pos < rhs.pos;     if (lhs.cnt != rhs.cnt) return lhs.cnt < rhs.cnt;     return false;   }   int main() {     int n;     cin >> n;     string s;     cin >> s;     vector<int> jump(s.size() + 1, 0);     for (int i = 0; i <= s.size(); i++) {       int to = 0;       for (int j = 0; j < i; j++) {         bool ok = true;         for (int k = 0; k < j; k++) {           ok &= (s[k] == s[i - j + k]);         }         if (i != s.size()) ok &= (s[j] != s[i]);         if (ok) to = j + 1 - (int)(i == s.size());       }       jump[i] = to;     }     set<string> subs;     for (int i = 0; i < s.size(); i++) {       for (int j = i + 1; j <= s.size(); j++) {         string ss;         for (int k = i; k < j; k++) {           ss += s[k];         }         subs.insert(ss);       }     }     set<string> lasts;     string ss;     for (int i = s.size() - 1; i >= 0; i--) {       ss = s[i] + ss;       lasts.insert(ss);     }     map<State, ll> dp;     dp[State{-1,   , 0, 0}] = 1;     for (int i = 0; i < n; i++) {       map<State, ll> next;       for (auto &e : dp) {         int bk = e.first.bk;         string str = e.first.fr;         int pos = e.first.pos;         int cnt = e.first.cnt;         if (str !=  @ ) {           str += s[pos];           if (subs.count(str)) {             if (lasts.count(str)) {               bk = i;             }           } else {             str =  @ ;           }         }         if (++pos == s.size()) {           pos = jump[pos];           cnt = true;         }         next[State{bk, str, pos, cnt}] += e.second;         bk = e.first.bk;         str = e.first.fr;         pos = e.first.pos;         cnt = e.first.cnt;         if (str !=  @ ) {           str += (s[pos] ==  0  ?  1  :  0 );           if (subs.count(str)) {             if (lasts.count(str)) {               bk = i;             }           } else {             str =  @ ;           }         }         pos = jump[pos];         next[State{bk, str, pos, cnt}] += e.second;       }       dp = next;     }     ll res = 0;     for (auto &e : dp) {       int bk = e.first.bk;       string strs = e.first.fr;       int pos = e.first.pos;       int cnt = e.first.cnt;       string str;       for (int i = 0; i < e.first.pos; i++) {         str += s[i];       }       for (int i = s.size() - e.first.bk - 1; i < s.size(); i++) {         str += s[i];       }       for (int i = 0; i <= (int)str.size() - (int)s.size(); i++) {         if (s == str.substr(i, s.size())) {           cnt = true;         }       }       if (cnt >= 1) {         res += e.second;       }     }     cout << res << endl;     return 0;   }   