func_code_string: #include <bits/stdc++.h>   using namespace std;   long long nxt[45][3], lnk[45], pre[45][3];   string s;   long long n;   pair<long long, long long> sh[45][45][2];   long long dp[41][41][41][41][2];   long long sol(long long i, long long pre, long long l, long long r,                 long long f = 0) {     if (pre == s.size()) f = 1;     if (r - l + 1 == s.size()) f = 1;     if (i == n) {       if (f) return 1;       string final;       if (pre) final = s.substr(0, pre);       if (r - l + 1) final += s.substr(l, r - l + 1);       if (final.find(s) != string::npos) {         return 1;       }       return 0;     }     if (~dp[i][pre][l][r][f]) return dp[i][pre][l][r][f];     if (r - l + 1 == i)       dp[i][pre][l][r][f] =           sol(i + 1, nxt[pre][0], sh[l][r][0].first, sh[l][r][0].second, f) +           sol(i + 1, nxt[pre][1], sh[l][r][1].first, sh[l][r][1].second, f);     else       dp[i][pre][l][r][f] =           sol(i + 1, nxt[pre][0], l, r, f) + sol(i + 1, nxt[pre][1], l, r, f);     return dp[i][pre][l][r][f];   }   void solve() {     cin >> n;     cin >> s;     for (long long i = 0; i < s.size(); i++) {       if (i > 1) {         lnk[i] = nxt[lnk[i - 1]][s[i - 1] -  0 ];       }       for (long long j = 0; j < 2; j++) {         if (s[i] == j +  0 )           nxt[i][j] = i + 1;         else if (i > 0) {           nxt[i][j] = nxt[lnk[i]][j];         }       }     }     for (long long i = 0; i < s.size(); i++) {       for (long long j = 0; j < s.size(); j++) {         for (long long k = 0; k < 2; k++) {           string pt;           if (j >= i) pt += s.substr(i, j - i + 1);           pt.push_back(k +  0 );           long long x = s.find(pt);           if (x != string::npos)             sh[i][j][k] = {x, x + j - i + 1};           else             sh[i][j][k] = {i, j};         }       }     }     if (s.size() == 1) {       long long x = s.back() -  0 ;       sh[1][0][x] = {0, 0};       sh[1][0][!x] = {1, 0};     }     memset(dp, -1, sizeof dp);     cout << sol(0, 0, 1, 0, 0) << endl;   }   int32_t main() {     ios::sync_with_stdio(false);     cin.tie(0);     long long t = 1;     while (t--) {       solve();     }     return 0;   }   