#include <bits/stdc++.h>
using namespace std;
const int maxN = 3000 + 5;
const int mod = 1000 * 1000 * 1000 + 7;
string p[maxN], s[maxN];
int dp[maxN];
string first;
int f[maxN];
int cnt(string &tmp) {
  int pos = 0, te = 0;
  for (int i = 0; i < (((int)tmp.size())); i++) {
    while (pos && (pos == (((int)first.size())) || first[pos] != tmp[i]))
      pos = f[pos - 1];
    if (first[pos] == tmp[i]) pos++;
    if (pos == (((int)first.size()))) te++;
  }
  return te;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  s[1] = p[1] = "a";
  s[2] = p[2] = "b";
  for (int i = 3; i <= 20; i++) {
    s[i] = s[i - 1] + s[i - 2];
    p[i] = p[i - 1] + p[i - 2];
  }
  p[19] = p[19].substr(0, 3100);
  s[19] = s[19].substr(s[19].size() - 3100);
  p[20] = p[20].substr(0, 3100);
  s[20] = s[20].substr(s[20].size() - 3100);
  for (int i = 21; i <= 3000; i++) {
    p[i] = p[i - 1];
    s[i] = s[i - 2];
  }
  int k, m;
  cin >> k >> m;
  for (int i = 0; i < m; i++) {
    cin >> first;
    fill(dp, dp + k + 1, 0);
    if (first == "a") dp[1] = 1;
    if (first == "b") dp[2] = 1;
    int pos = 0;
    fill(f, f + (((int)first.size())), 0);
    for (int j = 1; j < (((int)first.size())); j++) {
      while (pos && first[pos] != first[j]) pos = f[pos - 1];
      if (first[pos] == first[j]) pos++;
      f[j] = pos;
    }
    for (int j = 3; j <= k; j++) {
      dp[j] = dp[j - 1] + dp[j - 2];
      if (dp[j] >= mod) dp[j] -= mod;
      string tmp;
      for (int z = max(0, (((int)s[j - 1].size())) - (((int)first.size())) + 1);
           z < (((int)s[j - 1].size())); z++)
        tmp += s[j - 1][z];
      for (int z = 0;
           z < min((((int)p[j - 2].size())), (((int)first.size())) - 1); z++)
        tmp += p[j - 2][z];
      dp[j] += cnt(tmp);
      if (dp[j] >= mod) dp[j] -= mod;
    }
    cout << dp[k] << endl;
  }
  return 0;
}
