#include <bits/stdc++.h>
using namespace std;
int n, m, d[8037], b[2];
string f[27], s, a[2], ps;
void pre(void) {
  f[1] = "a";
  f[2] = "b";
  for (int i = 3; f[i - 1].length() < 8037; ++i)
    f[i] = f[i - 1] + f[i - 2], m = i;
  a[m % 2] = f[m];
  a[(m - 1) % 2] = f[m - 1];
}
void din(void) {
  int len = s.length(), del, le;
  b[0] = b[1] = 0;
  for (int i = 0; i < 2; ++i) {
    ps = a[i] + f[m], del = a[i].length();
    le = ps.length();
    for (int j = 0; j + len <= le; ++j)
      if (j < del && j + len > del && ps.substr(j, len) == s) b[i]++;
  }
  d[1] = (s == "a" ? 1 : 0);
  d[2] = (s == "b" ? 1 : 0);
  for (int i = 3; i <= n; ++i) {
    d[i] = d[i - 1] + d[i - 2];
    if (i <= m) {
      ps = f[i], del = f[i - 1].length();
      le = ps.length();
      for (int j = 0; j + len <= le; ++j)
        if (j < del && j + len > del && ps.substr(j, len) == s) d[i]++;
    } else
      d[i] += b[(i - 1) % 2];
    if (d[i] >= 1000000007) d[i] -= 1000000007;
  }
  cout << d[n] << "\n";
}
int main() {
  int t;
  pre();
  cin >> n >> t;
  while (t--) {
    cin >> s;
    din();
  }
  return 0;
}
