func_code_string: #include <bits/stdc++.h>   using namespace std;   struct mat {     int num[4][4];   };   int p[100009];   mat mult(mat &a, mat &b) {     mat ret;     for (int i = 0; i < 4; i++)       for (int j = 0; j < 4; j++) {         long long t = 0;         for (int k = 0; k < 4; k++) t += 1ll * a.num[i][k] * b.num[k][j];         ret.num[i][j] = t % 1000000007;       }     return ret;   }   int cal(string &a, string &b) {     if (b.size() > a.size()) return 0;     int ret = 0;     p[0] = -1;     for (int j, i = 0; b[i]; i++) {       for (j = p[i]; j >= 0 && b[i] != b[j]; j = p[j])         ;       p[i + 1] = j + 1;     }     for (int j = 0, i = 0; a[i]; i++) {       for (; j >= 0 && a[i] != b[j]; j = p[j])         ;       j++;       if (j == b.size()) ret++, j = p[j];     }     return ret;   }   mat m1, m2;   int query(long long n, string &q) {     if (n == 1) {       return q ==  a  ? 1 : 0;     }     if (n == 2) {       return q ==  b  ? 1 : 0;     }     string s1 =  a , s2 =  b , s =  b ;     for (n -= 2; n && s1.size() < q.size(); n--, s1 = s2, s2 = s) s = s2 + s1;     int f1 = cal(s1, q), f2 = cal(s, q);     if (!n) return f2;     s = s2.substr(s2.size() - q.size() + 1, q.size() - 1) +         s2.substr(0, q.size() - 1);     int t1 = cal(s, q);     s = s1.substr(s1.size() - q.size() + 1, q.size() - 1) +         s1.substr(0, q.size() - 1);     int t2 = cal(s, q);     m1.num[0][0] = m1.num[0][1] = m1.num[0][2] = m1.num[1][0] = m1.num[2][2] =         m1.num[3][3] = 1;     m2.num[0][0] = m2.num[0][1] = m2.num[0][3] = m2.num[1][0] = m2.num[2][2] =         m2.num[3][3] = 1;     mat res, t = mult(m2, m1);     bool flag = 0;     if (n % 2) res = m1, flag = 1;     for (n /= 2; n; n >>= 1, t = mult(t, t))       if (n & 1) {         if (!flag)           res = t, flag = 1;         else           res = mult(res, t);       }     return (1ll * res.num[0][0] * f2 + 1ll * res.num[0][1] * f1 +             1ll * res.num[0][2] * t1 + 1ll * res.num[0][3] * t2) %            1000000007;   }   int main() {     long long n, m;     cin >> n >> m;     string s;     while (m--) cin >> s, cout << query(n, s) << endl;   }   