#include <bits/stdc++.h>   using namespace std;   const long long N = 4, M = 1e5 + 10, Mo = 1e9 + 7;   long long n, m, nxt[M], p, lena, lenb, lens;   string aa, bb, s;   struct Matrix {     long long n, a[N][N];     Matrix(long long _n = 4) { n = _n, memset(a, 0, sizeof(a)); }     void operator~() {       for (long long i = 0; i < 4; i++) a[i][i] = 1;     }     Matrix operator+(const Matrix &b) const {       Matrix ret(4);       for (long long i = 0; i < 4; i++)         for (long long j = 0; j < 4; j++)           ret.a[i][j] = (a[i][j] + b.a[i][j]) % Mo;       return ret;     }     Matrix operator-(const Matrix &b) const {       Matrix ret(4);       for (long long i = 0; i < 4; i++)         for (long long j = 0; j < 4; j++)           ret.a[i][j] = (a[i][j] - b.a[i][j] + Mo) % Mo;       return ret;     }     Matrix operator*(const Matrix &b) const {       Matrix ret(4);       for (long long i = 0; i < 4; i++)         for (long long j = 0; j < 4; j++)           for (long long k = 0; k < 4; k++)             ret.a[i][k] =                 (ret.a[i][k] + 1LL * a[i][j] * b.a[j][k] % Mo + Mo) % Mo;       return ret;     }     Matrix operator^(const long long &b) const {       Matrix ret, x, m1, m2;       for (long long i = 0; i < 4; i++)         for (long long j = 0; j < 4; j++)           if (i == j)             ret.a[i][j] = 1;           else             ret.a[i][j] = 0;       for (long long i = 0; i < 4; i++)         for (long long j = 0; j < 4; j++) m1.a[i][j] = m2.a[i][j] = 0;       m1.a[0][0] = m1.a[0][1] = m1.a[1][0] = m1.a[2][2] = m1.a[2][3] =           m1.a[3][2] = m2.a[0][0] = m2.a[0][1] = m2.a[1][0] = m2.a[2][0] =               m2.a[3][2] = 1;       x = m2 * m1;       for (long long B = b >> 1; B; B >>= 1, x = x * x) {         if (B & 1) ret = ret * x;       }       if (b & 1) ret = m1 * ret;       return ret;     }   } a, b, c, m1, m2;   inline long long read() {     long long x = 0, k = 1;     char c = getchar();     for (; c < 48 || c > 57; c = getchar()) k ^= (c ==  - );     for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);     return k ? x : -x;   }   long long kmp1(long long l, long long r) {     long long ans = 0;     for (long long i = 0, p = 0; i < r; i++) {       for (; (~p) && s[p] != aa[i]; p = nxt[p])         ;       p = p + 1;       if (p == lens && i >= l && i <= r - 1)         ans = ans + 1, p = nxt[p];       else if (p == lens)         p = nxt[p];     }     return ans;   }   long long kmp2(long long l, long long r) {     long long ans = 0;     for (long long i = 0, p = 0; i < r; i++) {       for (; (~p) && s[p] != bb[i]; p = nxt[p])         ;       p = p + 1;       if (p == lens && i >= l && i <= r - 1)         ans = ans + 1, p = nxt[p];       else if (p == lens)         p = nxt[p];     }     return ans;   }   long long KMP(const string &b, long long l, long long r) {     long long ans = 0;     long long lenb = b.length();     for (long long i = 0, p = 0; i < lenb; i++) {       for (; (~p) && s[p] != b[i]; p = nxt[p])         ;       p = p + 1;       if (p == lens && i >= l && i <= r - 1)         ans = ans + 1, p = nxt[p];       else if (p == lens)         p = nxt[p];     }     return ans;   }   signed main() {     m1.a[0][0] = m1.a[0][1] = m1.a[1][0] = m1.a[2][2] = m1.a[2][3] = m1.a[3][2] =         m2.a[0][0] = m2.a[0][1] = m2.a[1][0] = m2.a[2][0] = m2.a[3][2] = 1;     std::ios::sync_with_stdio(false);     std::cin >> n;     long long T;     std::cin >> T;     for (long long x; T--;) {       std::cin >> s;       aa =  a , bb =  b ;       lena = aa.length(), lenb = bb.length(), lens = s.length(), nxt[0] = -1,       p = 0;       ;       for (long long i = 0; i < lens; i++) {         for (p = nxt[i]; (~p) && s[p] != s[i]; p = nxt[p])           ;         nxt[i + 1] = ++p;       }       if (n == 1) {         printf( %lld n , kmp1(0, lena));       } else if (n == 2) {         printf( %lld n , kmp2(0, lenb));       } else {         for (x = 1; lena < lens && x <= n; ++x) {           aa = bb + aa;           std::swap(aa, bb);           lena = aa.length();         }         lenb = bb.length();         if (x > n)           printf( 0 n );         else if (x == n)           printf( %lld n , kmp1(0, lena));         else {           lena = aa.length(), lenb = bb.length(), lens = s.length();           long long tt = n - x - 1;           c = c ^ tt;           printf( %lld n ,                  (c.a[0][0] % Mo * kmp2(0, lenb) % Mo +                   c.a[1][0] % Mo * KMP(bb + aa, lenb, lena + lenb) % Mo +                   c.a[2][0] % Mo * KMP(aa + bb, lena, lena + lens - 1) % Mo +                   c.a[3][0] % Mo * KMP(bb + bb, lenb, lenb + lens - 1) % Mo) %                      Mo);         }       }     }     return 0;   }   