#include <bits/stdc++.h>
using namespace std;
template <class T>
struct Matrix {
  int r, c;
  T a[4][4];
  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*(const 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]) % 1000000007;
    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 Next[1000000];
int KMP(string A, string B) {
  int l = A.length();
  A = A + "#" + B;
  Next[0] = -1;
  int x = -1, ret = 0;
  for (int i = 1; i < A.length(); ++i) {
    while (x >= 0 && A[x + 1] != A[i]) x = Next[x];
    if (A[x + 1] == A[i]) x++;
    Next[i] = x;
    if (Next[i] == l - 1) ret++;
  }
  return ret;
}
int main() {
  Matrix<int> M;
  string fs[30];
  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];
  string instr;
  long long k;
  int m;
  cin >> k >> m;
  while (m--) {
    cin >> instr;
    if (k < 30) {
      cout << KMP(instr, fs[k]) << endl;
      continue;
    }
    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> cnt;
    cnt.r = 1;
    cnt.c = 4;
    cnt.a[0][1] = 1;
    cnt = cnt * (M ^ (k - I - 1));
    long long ans = (cnt.a[0][0] * (CBA + CA) + cnt.a[0][1] * CB +
                     cnt.a[0][2] * CAB + cnt.a[0][3] * CBB) %
                    1000000007;
    cout << ans << endl;
  }
  return 0;
}
