#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
const int MOD = 1000000007;
const int fsz = 2;
struct matrix {
  int mas[5][5];
};
matrix operator*(matrix &a, matrix &b) {
  matrix c;
  for (int i = 1; i <= fsz; ++i)
    for (int j = 1; j <= fsz; ++j) {
      c.mas[i][j] = 0;
      for (int k = 1; k <= fsz; ++k)
        c.mas[i][j] =
            (c.mas[i][j] + (unsigned long long)a.mas[i][k] * b.mas[k][j]) % MOD;
    }
  return c;
}
matrix pow(matrix a, int times) {
  matrix c;
  for (int i = 1; i <= fsz; ++i)
    for (int j = 1; j <= fsz; ++j) c.mas[i][j] = (i == j);
  while (times) {
    if (times & 1) c = c * a;
    a = a * a;
    times /= 2;
  }
  return c;
}
int getfibb(int n) {
  matrix a;
  memset(a.mas, 0, sizeof(a.mas));
  a.mas[1][1] = 0;
  a.mas[1][2] = 1;
  a.mas[2][1] = a.mas[2][2] = 1;
  a = pow(a, n - 1);
  return a.mas[2][2];
}
int pr[2000000];
int cnt(string a, string b) {
  string cur = a + "c" + b;
  pr[0] = 0;
  int ans = 0;
  for (int i = 1; i <= (int)(cur).size() - 1; ++i) {
    int j = pr[i - 1];
    while (j && cur[i] != cur[j]) j = pr[j - 1];
    if (cur[i] == cur[j]) ++j;
    pr[i] = j;
    if (i > (int)(a).size() && pr[i] >= (int)(a).size()) ++ans;
  }
  return ans;
}
int over(string f1, string f2, string s) {
  string cur = s + "c" + f1 + f2;
  pr[0] = 0;
  int ans = 0;
  for (int i = 1; i <= (int)(cur).size() - 1; ++i) {
    int j = pr[i - 1];
    while (j && cur[i] != cur[j]) j = pr[j - 1];
    if (cur[i] == cur[j]) ++j;
    pr[i] = j;
    int id = i - (int)(s).size() - 1;
    if (id >= (int)(f1).size() && id - (int)(s).size() + 1 < (int)(f1).size() &&
        pr[i] >= (int)(s).size())
      ++ans;
  }
  return ans;
}
int id;
string f[1000];
int get_answer(int n, string &s) {
  int v = 2;
  while ((int)(f[v]).size() <= (int)(s).size() ||
         (int)(f[v - 1]).size() <= (int)(s).size())
    ++v;
  if (v >= n) return cnt(s, f[n]);
  string F = f[v] + f[v - 1];
  int k1 = over(f[v], f[v - 1], s), k2 = over(F, f[v], s), b = cnt(s, f[v]),
      a = cnt(s, f[v - 1]);
  for (int i = v + 1; i <= n; ++i) {
    int c = b;
    if (i % 2 == v % 2)
      b = (0LL + b + a + k2) % MOD;
    else
      b = (0LL + b + a + k1) % MOD;
    a = c;
  }
  return b;
}
string s;
int main() {
  f[1] = "a";
  f[2] = "b";
  id = 2;
  for (;;) {
    ++id;
    f[id] = f[id - 1] + f[id - 2];
    if ((int)(f[id]).size() > 100000 && (int)(f[id - 1]).size() > 100000) break;
  }
  int n, query;
  cin >> n >> query;
  while (query--) {
    cin >> s;
    cout << get_answer(n, s) << endl;
  }
}
