#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const double CLOCKS_PER_SECOND = ((clock_t)1000);
clock_t st, fi;
long long n, m;
int nex[N];
string tmp, s[30];
struct Matrix {
  int n, m;
  int a[5][5];
} u, v, f;
Matrix operator*(Matrix x, Matrix y) {
  Matrix z;
  z.n = x.n;
  z.m = y.m;
  for (int i = 1; i <= x.n; i++) {
    for (int j = 1; j <= y.m; j++) {
      int ans = 0;
      for (int k = 1; k <= x.m; k++) {
        ans += 1LL * x.a[i][k] * y.a[k][j] % mod;
        if (ans >= mod) ans -= mod;
      }
      z.a[i][j] = ans;
    }
  }
  return z;
}
Matrix operator^(Matrix x, long long p) {
  Matrix ans;
  ans.n = ans.m = x.n;
  memset(ans.a, 0, sizeof(ans.a));
  for (int i = 1; i <= x.n; i++) ans.a[i][i] = 1;
  while (p) {
    if (p & 1) ans = ans * x;
    x = x * x;
    p >>= 1;
  }
  return ans;
}
void Kmp_init() {
  int k = -1, j = 0;
  nex[0] = -1;
  int plen = tmp.size();
  while (j < plen) {
    while (k != -1 && tmp[k] != tmp[j]) k = nex[k];
    nex[++j] = ++k;
  }
}
int Kmp(string &s) {
  int j = 0, k = 0, ans = 0, slen = s.size(), plen = tmp.size();
  while (j < slen) {
    while (k != -1 && s[j] != tmp[k]) k = nex[k];
    j++;
    k++;
    if (k == plen) ans++, k = nex[k];
  }
  return ans;
}
void Solve() {
  cin >> tmp;
  int x;
  for (x = 1; s[x].size() < tmp.size(); x++)
    ;
  if (x > n) {
    puts("0");
    return;
  }
  Kmp_init();
  int a = Kmp(s[x]), b = Kmp(s[x + 1]), c = Kmp(s[x + 2]), d = Kmp(s[x + 3]);
  d = d - b - c;
  c = c - a - b;
  if (x == n) {
    cout << a << endl;
    return;
  }
  if (x == n + 1) {
    cout << b << endl;
    return;
  }
  long long k = n - x - 1;
  f.n = 1;
  f.m = 3;
  f.a[1][1] = a;
  f.a[1][2] = b;
  f.a[1][3] = 1;
  u.n = u.m = 3;
  u.a[1][1] = 0;
  u.a[1][2] = 1;
  u.a[1][3] = 0;
  u.a[2][1] = 1;
  u.a[2][2] = 1;
  u.a[2][3] = 0;
  u.a[3][1] = 0;
  u.a[3][2] = c;
  u.a[3][3] = 1;
  v.n = v.m = 3;
  v.a[1][1] = 0;
  v.a[1][2] = 1;
  v.a[1][3] = 0;
  v.a[2][1] = 1;
  v.a[2][2] = 1;
  v.a[2][3] = 0;
  v.a[3][1] = 0;
  v.a[3][2] = d;
  v.a[3][3] = 1;
  Matrix t = u * v;
  t = t ^ (k / 2);
  if (k & 1) t = t * u;
  f = f * t;
  cout << f.a[1][2] << endl;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  s[1] = "a";
  s[2] = "b";
  for (int i = 3; i <= 29; i++) s[i] = s[i - 1] + s[i - 2];
  while (m--) Solve();
  return 0;
}
