#include <bits/stdc++.h>
const int mod = 1000000007;
const int MAXL = 1000000;
using namespace std;
long long k;
long long f[30];
int z[MAXL];
char s[MAXL], tmp[MAXL], tmp1[MAXL];
char buf[10 * MAXL];
char *curuk = buf;
char *fstr[30];
struct matrix {
  int n;
  int a[20][20];
  int c[20][20];
  void output() {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) printf("%d%c", a[i][j], " \n"[j + 1 == n]);
  }
  void operator*=(const matrix &b) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        c[i][j] = 0;
        for (int k = 0; k < n; k++)
          c[i][j] = (c[i][j] + 1LL * a[i][k] * b.a[k][j]) % mod;
      }
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) a[i][j] = c[i][j];
  }
  void proc(int N) {
    n = N;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) a[i][j] = i == j;
  }
};
matrix A, m1, m2, m3, res;
inline int eq(char *a, char *b) {
  int n = strlen(a), m = strlen(b);
  strcat(a, "c");
  strcat(a, b);
  int ret = 0;
  for (int i = 1, l = 0; a[i]; i++) {
    z[i] = (l + z[l] > i ? min(l + z[l] - i, z[i - l]) : 0);
    for (; a[z[i]] == a[i + z[i]]; z[i]++)
      ;
    if (i + z[i] > l + z[l]) l = i;
    if (z[i] == n) ret++;
  }
  return ret;
}
inline int main2() {
  long long ret = 0;
  scanf("%s", s);
  int n = strlen(s);
  if (k < 28 && f[k] < n) return 0;
  if (k < 28 && f[k - 1] < n) return eq(s, fstr[k]);
  int i = 1;
  long long toN, amo;
  for (; f[i] < n; i++)
    ;
  toN = k - i - 1;
  res.proc(m1.n);
  A = m1;
  for (; toN > 0;)
    if (toN & 1)
      toN--, res *= A;
    else
      toN >>= 1, A *= A;
  strcpy(tmp, s);
  amo = eq(tmp, fstr[i + 1]);
  ret = (ret + amo * (res.a[0][0] + res.a[0][3])) % mod;
  strcpy(tmp, s);
  amo = eq(tmp, fstr[i]);
  ret = (ret + amo * (res.a[1][0] + res.a[1][3])) % mod;
  if (k >= i + 2) {
    res.proc(m2.n);
    A = m2;
    toN = k - i - 2;
    for (; toN > 0;)
      if (toN & 1)
        toN--, res *= A;
      else
        toN >>= 1, A *= A;
    strcpy(tmp1, fstr[i + 1] + f[i + 1] - n + 1);
    strcat(tmp1, fstr[i]);
    tmp1[n + n - 2] = 0;
    strcpy(tmp, s);
    amo = eq(tmp, tmp1);
    ret = (ret + amo * res.a[0][0]) % mod;
  }
  if (k >= i + 1) {
    res.proc(m3.n);
    A = m3;
    toN = (k - i - 1) / 2;
    for (; toN > 0;)
      if (toN & 1)
        toN--, res *= A;
      else
        toN >>= 1, A *= A;
    strcpy(tmp1, fstr[i] + f[i] - n + 1);
    strcat(tmp1, fstr[i + 1]);
    tmp1[n + n - 2] = 0;
    strcpy(tmp, s);
    amo = eq(tmp, tmp1);
    ret = (ret + amo * res.a[(k - i) % 2][2]) % mod;
  }
  if (k >= i + 2) {
    res.proc(m3.n);
    A = m3;
    toN = (k - i - 2) / 2;
    for (; toN > 0;)
      if (toN & 1)
        toN--, res *= A;
      else
        toN >>= 1, A *= A;
    strcpy(tmp1, fstr[i + 1] + f[i + 1] - n + 1);
    strcat(tmp1, fstr[i + 1]);
    tmp1[n + n - 2] = 0;
    strcpy(tmp, s);
    amo = eq(tmp, tmp1);
    ret = (ret + amo * res.a[1 ^ ((k - i) % 2)][2]) % mod;
  }
  return ret;
}
int main() {
  fstr[0] = curuk;
  curuk += 1;
  strcpy(curuk, "a");
  fstr[1] = curuk;
  curuk += 2;
  strcpy(curuk, "b");
  fstr[2] = curuk;
  curuk += 2;
  f[1] = f[2] = 1;
  for (int i = 3; i <= 27; i++) {
    f[i] = f[i - 1] + f[i - 2];
    fstr[i] = curuk;
    strcpy(curuk, fstr[i - 1]);
    strcat(curuk, fstr[i - 2]);
    curuk += f[i] + 1;
  }
  m1.n = 4;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (!((i + j) & 1))
        m1.a[i][j] = 1;
      else
        m1.a[i][j] = 0;
  m1.a[2][2] = m1.a[3][3] = 0;
  m2.n = 2;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      if (i && j)
        m2.a[i][j] = 0;
      else
        m2.a[i][j] = 1;
  m3.n = 3;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) m3.a[i][j] = 1;
  m3.a[0][0] = 2;
  m3.a[2][0] = m3.a[2][1] = 0;
  cin >> k;
  int test_num;
  scanf("%d", &test_num);
  for (; test_num--;) printf("%d\n", main2());
  return 0;
}
