#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T &x) {
  x = 0;
  char c = getchar();
  long long f = 0;
  while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (f) x = -x;
}
template <class T>
bool checkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const long long mod = 1e9 + 7;
template <class T>
void my_add(T &a, T b) {
  a = a + b > mod ? a + b - mod : a + b;
}
template <class T>
void my_sub(T &a, T b) {
  a = a - b < 0 ? a - b + mod : a - b;
}
long long F[100], B[100], C[100];
void trry() {
  F[0] = 0;
  F[1] = 1;
  cout << "F: ";
  for (long long i = 2; i <= 20; ++i)
    cout << (F[i] = (F[i - 1] + F[i - 2])) << " ";
  cout << endl;
  B[0] = 0;
  B[1] = 0;
  cout << "B: ";
  for (long long i = 2; i <= 20; ++i)
    cout << (B[i] = (B[i - 1] + B[i - 2] + (i % 2 == 0))) << " ";
  cout << endl;
  C[0] = 0;
  C[1] = 1;
  cout << "C: ";
  for (long long i = 2; i <= 20; ++i)
    cout << (C[i] = (C[i - 1] + C[i - 2] + (i % 2 == 1))) << " ";
  cout << endl;
}
namespace moonpie {
const long long N = 1e5 + 5, mh = 998244353;
long long n, m, len, base, F[30], nxt[N];
string s, t, Fs[30], F1, F2;
long long get_num(string a) {
  long long res = 0;
  for (long long i = 0, j = 0; i < a.length(); ++i) {
    while (j >= 0 && t[j + 1] != a[i]) j = nxt[j];
    if (++j == len) ++res, j = nxt[j];
  }
  return res;
}
struct matrix_base {
  long long ma[2][2];
} bm;
struct matrix_ans {
  long long ma[2];
} ans;
inline void mul_base() {
  matrix_base res;
  memset(res.ma, 0, sizeof(res.ma));
  for (long long i = 0; i < 2; ++i)
    for (long long j = 0; j < 2; ++j)
      for (long long k = 0; k < 2; ++k)
        my_add(res.ma[i][j], bm.ma[i][k] * bm.ma[k][j] % mod);
  bm = res;
}
inline void mul_ans() {
  matrix_ans res;
  memset(res.ma, 0, sizeof(res.ma));
  for (long long i = 0; i < 2; ++i)
    for (long long j = 0; j < 2; ++j)
      my_add(res.ma[i], ans.ma[j] * bm.ma[j][i] % mod);
  ans = res;
}
long long calc() {
  len = s.length();
  t = "%" + s;
  nxt[0] = -1;
  for (long long i = 2, j = 0; i <= len; ++i) {
    while (j >= 0 && t[j + 1] != t[i]) j = nxt[j];
    nxt[i] = ++j;
  }
  F[1] = F[2] = 1;
  Fs[1] = "a";
  Fs[2] = "b";
  for (long long i = 3;; ++i) {
    if (F[i - 2] > len) {
      Fs[i] = Fs[i - 1] + Fs[i - 2];
      base = i - 1;
      break;
    }
    F[i] = F[i - 1] + F[i - 2];
    Fs[i] = Fs[i - 1] + Fs[i - 2];
  }
  string a, b, c;
  for (long long i = 0; i < len - 1; ++i) a += Fs[base - 1][i];
  for (long long i = Fs[base - 1].length() - (len - 1);
       i < Fs[base - 1].length(); ++i)
    b += Fs[base - 1][i];
  for (long long i = Fs[base].length() - (len - 1); i < Fs[base].length(); ++i)
    c += Fs[base][i];
  long long vc = get_num(c + a);
  long long vb = get_num(b + a);
  if (n - base <= 1) {
    return get_num(Fs[n]);
  }
  ans.ma[0] = 0;
  ans.ma[1] = 1;
  memset(bm.ma, 0, sizeof(bm.ma));
  bm.ma[0][1] = bm.ma[1][0] = bm.ma[1][1] = 1;
  long long y = n - base;
  for (long long i = 0; (1ll << i) <= y; ++i, mul_base())
    if (y & (1ll << i)) mul_ans();
  long long B = ans.ma[0] - (y % 2 == 1);
  ans.ma[0] = 0;
  ans.ma[1] = 1;
  memset(bm.ma, 0, sizeof(bm.ma));
  bm.ma[0][1] = bm.ma[1][0] = bm.ma[1][1] = 1;
  for (long long i = 0; (1ll << i) <= y - 1; ++i, mul_base())
    if ((y - 1) & (1ll << i)) mul_ans();
  long long C = ans.ma[0] - ((y - 1) % 2 == 1);
  ans.ma[0] = get_num(Fs[base]);
  ans.ma[1] = get_num(Fs[base] + Fs[base - 1]);
  memset(bm.ma, 0, sizeof(bm.ma));
  bm.ma[0][1] = bm.ma[1][0] = bm.ma[1][1] = 1;
  for (long long i = 0; (1ll << i) <= y; ++i, mul_base())
    if (y & (1ll << i)) mul_ans();
  return (ans.ma[0] + B * vb % mod + C * vc % mod) % mod;
}
void solve() {
  cin >> n >> m;
  for (long long i = 1; i <= m; ++i) {
    cin >> s;
    printf("%lld\n", calc());
  }
}
}  // namespace moonpie
signed main() {
  moonpie::solve();
  return 0;
}
