#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;
}
