#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<int> pow(Matrix<int> a, long long b) {
  Matrix<int> ret(4), base = a;
  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 = 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;
  for (int i = (0); i < (m); ++i) {
    cin >> instr;
    cout << go() << endl;
  }
  return 0;
}
