#include <bits/stdc++.h>
using namespace std;
int k, q, n, ton[3005][2], p[3005], dprefix[3005][2], pass, premark[3005][2],
    dfib[3005][3005], fibmark[3005][3005], dp[3005][3005], mark[3005][3005];
char s[3005];
void pfunc() {
  for (int i = 2; i <= n; i++) {
    p[i] = p[i - 1];
    while (p[i] > 0 && s[p[i]] != s[i - 1]) p[i] = p[p[i]];
    if (s[i - 1] == s[p[i]]) p[i]++;
  }
}
int ppfunc(int i, int c) {
  if (premark[i][c] == pass) return dprefix[i][c];
  premark[i][c] = pass;
  if (p[i] > 0 && s[p[i]] != c) return dprefix[i][c] = ppfunc(p[i], c);
  return dprefix[i][c] = p[i] + (s[p[i]] == c);
}
void automaton() {
  ton[0][1] = ton[0][0] = 0;
  ton[0][s[0]] = 1;
  for (int i = 1; i <= n; i++) {
    if (i == n) {
      ton[i][1] = ppfunc(i, 1);
      ton[i][0] = ppfunc(i, 0);
      continue;
    }
    if (s[i] == 0) {
      ton[i][0] = i + 1;
      ton[i][1] = ppfunc(i, 1);
    } else {
      ton[i][1] = i + 1;
      ton[i][0] = ppfunc(i, 0);
    }
  }
}
int automafib(int s, int k) {
  if (k == 1) return dfib[s][k] = ton[s][0];
  if (k == 2) return dfib[s][k] = ton[s][1];
  if (fibmark[s][k] == pass) return dfib[s][k];
  fibmark[s][k] = pass;
  int x = automafib(s, k - 1);
  return dfib[s][k] = automafib(x, k - 2);
}
int f(int k, int s) {
  if (k == 1) return ton[s][0] == n;
  if (k == 2) return ton[s][1] == n;
  if (mark[k][s] == pass) return dp[k][s];
  mark[k][s] = pass;
  int x = dfib[s][k - 1];
  return dp[k][s] = (f(k - 1, s) + f(k - 2, x)) % 1000000007;
}
int main() {
  scanf("%d %d", &k, &q);
  while (q--) {
    pass++;
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; i++) s[i] -= 'a';
    p[1] = 0;
    pfunc();
    automaton();
    for (int i = 1; i <= k; i++)
      for (int j = 0; j <= n; j++) automafib(j, i);
    printf("%d\n", f(k, 0));
  }
  return 0;
}
