func_code_string: #include <bits/stdc++.h>   using namespace std;   const long long mod = 1e9 + 7;   const int maxn = 4;   template <class T>   struct Matrix {     int r, c;     T a[maxn][maxn];     Matrix() { memset(a, 0, sizeof a); }     Matrix(int si) {       memset(a, 0, sizeof a);       r = c = si;       for (int i = 0; i < si; i++) a[i][i] = 1;     }     Matrix operator*(Matrix &rhs) {       Matrix<T> ret;       ret.r = r;       ret.c = rhs.c;       for (int k = 0; k < c; ++k)         for (int i = 0; i < ret.r; ++i)           for (int j = 0; j < ret.c; ++j)             ret.a[i][j] = (ret.a[i][j] + (long long)a[i][k] * rhs.a[k][j]) % mod;       return ret;     }     Matrix operator^(long long b) {       Matrix<T> ret, base = *this;       int setret = 0;       while (b) {         if (b & 1) ret = (setret ? ret * base : base), setret = 1;         base = base * base;         b >>= 1;       }       return ret;     }   };   int P[1000000];   int KMP(string A, string B) {     int l = A.length();     A = A +  #  + B;     P[0] = -1;     int x = -1, ret = 0;     for (int i = (1); i < (A.length()); ++i) {       while (x >= 0 && A[x + 1] != A[i]) x = P[x];       if (A[x + 1] == A[i]) x++;       P[i] = x;       if (P[i] == l - 1) ret++;     }     return ret;   }   Matrix<int> M;   string fs[30];   string instr;   long long k;   int go() {     if (k < 30) return KMP(instr, fs[k]);     string A, B;     int I;     for (int i = 1; i < 30; i++) {       if (fs[i].length() >= instr.length()) {         B = fs[i + 1];         A = fs[i];         I = i;         break;       }     }     long long CA = KMP(instr, A);     long long CB = KMP(instr, B);     long long CBA = KMP(instr, B + A) - CB - CA;     long long CAB = KMP(instr, A + B) - CA - CB;     long long CBB = KMP(instr, B + B) - CB - CB;     Matrix<int> co, POW;     co.r = 1;     co.c = 4;     co.a[0][1] = 1;     POW = M ^ (k - I - 1);     co = co * POW;     return (co.a[0][0] * (CBA + CA) + co.a[0][1] * CB + co.a[0][2] * CAB +             co.a[0][3] * CBB) %            mod;   }   int main() {     ios_base::sync_with_stdio(0);     M.r = M.c = 4;     M.a[0][1] = M.a[0][2] = M.a[1][0] = M.a[1][1] = M.a[2][3] = M.a[3][2] = 1;     fs[1] =  a ;     fs[2] =  b ;     for (int i = 3; i < 30; ++i) fs[i] = fs[i - 1] + fs[i - 2];     int m;     cin >> k >> m;     while (m--) {       cin >> instr;       cout << go() << endl;     }     return 0;   }   