#include <bits/stdc++.h>
using namespace std;
bool SR(int &x) { return scanf("%d", &x) == 1; }
bool SR(long long &x) { return scanf("%lld", &x) == 1; }
bool SR(double &x) { return scanf("%lf", &x) == 1; }
bool SR(char *s) { return scanf("%s", s) == 1; }
bool RI() { return true; }
template <typename I, typename... T>
bool RI(I &x, T &...tail) {
  return SR(x) && RI(tail...);
}
void SP(const int x) { printf("%d", x); }
void SP(const long long x) { printf("%lld", x); }
void SP(const double x) { printf("%.16lf", x); }
void SP(const char *s) { printf("%s", s); }
void PL() { puts(""); }
template <typename I, typename... T>
void PL(const I x, const T... tail) {
  SP(x);
  if (sizeof...(tail)) putchar(' ');
  PL(tail...);
}
const int maxn = 3e3 + 3;
const int second = 200;
struct Node {
  static Node mem[maxn], *pmem;
  int dep;
  Node *fail, *to[2];
  int who;
  Node() : dep(-1), fail(0), to{NULL, NULL}, who(-1) {}
  Node(int _d, int _w) : dep(_d), fail(0), to{NULL, NULL}, who(_w) {}
} Node::mem[maxn], *Node::pmem = Node::mem;
struct AC {
  AC() { root = new (Node::pmem++) Node(-1, -1); }
  Node *root;
  void add(const string &s, int id) {
    Node *pt = root;
    for (int i = 0; i < int(((int)(s).size())); i++) {
      if (!pt->to[s[i] - 'a'])
        pt->to[s[i] - 'a'] = new (Node::pmem++) Node(1 + pt->dep, -1);
      pt = pt->to[s[i] - 'a'];
    }
    pt->who = id;
  }
  void build() {
    queue<Node *> q;
    q.push(root);
    root->fail = root;
    while (((int)(q).size())) {
      Node *pt = q.front();
      q.pop();
      for (int i = 0; i < int(2); i++)
        if (pt->to[i]) q.push(pt->to[i]);
      if (pt->dep == -1) {
        for (int i = 0; i < int(2); i++)
          if (pt->to[i]) pt->to[i]->fail = root;
        for (int i = 0; i < int(2); i++)
          if (!pt->to[i]) pt->to[i] = root;
      } else {
        for (int i = 0; i < int(2); i++)
          if (pt->to[i]) {
            Node *&cur = pt->to[i]->fail;
            for (cur = pt->fail; cur != root && !cur->to[i]; cur = cur->fail)
              ;
            if (cur->to[i]) cur = cur->to[i];
          }
        for (int i = 0; i < int(2); i++)
          if (!pt->to[i]) {
            Node *&cur = pt->to[i];
            for (cur = pt->fail; cur != root && !cur->to[i]; cur = cur->fail)
              ;
            if (cur->to[i]) cur = cur->to[i];
          }
      }
    }
  }
} ac;
int n, m;
string s[maxn];
void read() {
  RI(n, m);
  for (int i = 0; i < int(m); i++) {
    static char in[maxn];
    RI(in);
    s[i] = in;
  }
}
const int MOD = 1e9 + 7;
string os[maxn];
int sig;
int f[maxn][maxn];
int _c[2][maxn][maxn / second + 1];
int (*prv)[maxn / second + 1], (*cur)[maxn / second + 1];
int big;
int om;
void build() {
  om = m;
  for (int i = 0; i < int(m); i++) os[i] = s[i];
  sort(s, s + m);
  m = unique(s, s + m) - s;
  sort(s, s + m, [&](const string &a, const string &b) {
    return make_pair(((int)(a).size()), a) > make_pair(((int)(b).size()), b);
  });
  for (big = 0; big < m && ((int)(s[big]).size()) > second; big++)
    ;
  for (int i = 0; i < int(m); i++) ac.add(s[i], i);
  ac.build();
  sig = Node::pmem - Node::mem;
}
int ans[maxn];
void sol_big() {
  for (int i = 0; i < int(sig); i++) f[1][i] = Node::mem[i].to[0] - Node::mem;
  for (int i = 0; i < int(sig); i++) f[2][i] = Node::mem[i].to[1] - Node::mem;
  for (int i = (3); i <= int(n); i++)
    for (int j = 0; j < int(sig); j++) f[i][j] = f[i - 2][f[i - 1][j]];
  prv = _c[0];
  cur = _c[1];
  for (int i = 0; i < int(sig); i++)
    for (int j = 0; j < int(big); j++) {
      Node *pt = Node::mem + i;
      for (pt = pt->to[0]; pt->who != j && pt->dep != -1; pt = pt->fail)
        ;
      prv[i][j] = (pt->who == j);
    }
  for (int i = 0; i < int(sig); i++)
    for (int j = 0; j < int(big); j++) {
      Node *pt = Node::mem + i;
      for (pt = pt->to[1]; pt->who != j && pt->dep != -1; pt = pt->fail)
        ;
      cur[i][j] = (pt->who == j);
    }
  for (int _ = (3); _ <= int(n); _++) {
    static int tmp[maxn][maxn / second + 1];
    auto &m1 = cur, &m2 = prv;
    for (int i = 0; i < int(sig); i++)
      for (int j = 0; j < int(big); j++)
        tmp[i][j] = m1[i][j] + m2[f[_ - 1][i]][j];
    for (int i = 0; i < int(sig); i++)
      for (int j = 0; j < int(big); j++)
        if (tmp[i][j] >= MOD) tmp[i][j] -= MOD;
    swap(prv, cur);
    for (int i = 0; i < int(sig); i++)
      for (int j = 0; j < int(big); j++) cur[i][j] = tmp[i][j];
  }
  for (int i = 0; i < int(big); i++) ans[i] = cur[0][i];
}
string h[maxn], t[maxn];
int ap[maxn][maxn];
void merge(const string &p, const string &q, int res[]) {
  for (int i = 0; i < int(((int)(p).size())); i++) {
    Node *pt = ac.root;
    for (int j = (i); j <= int(((int)(p).size()) - 1); j++)
      pt = pt->to[p[j] - 'a'];
    for (int j = 0; j < int(((int)(q).size())); j++) {
      pt = pt->to[q[j] - 'a'];
      if (big <= pt->who && pt->who < m &&
          pt->dep == (((int)(p).size()) - i) + j)
        res[pt->who]++;
    }
  }
  for (int i = (big); i <= int(m - 1); i++)
    if (res[i] >= MOD) res[i] -= MOD;
}
void sol_small() {
  h[1] = "a";
  h[2] = "b";
  for (int i = (3); i <= int(15); i++) h[i] = h[i - 1] + h[i - 2];
  for (int i = (1); i <= int(15); i++) t[i] = h[i];
  if (n <= 15) {
    for (int j = (big); j <= int(m - 1); j++)
      for (size_t o = h[n].find(s[j]); ~o; o = h[n].find(s[j], o + 1)) ans[j]++;
  } else {
    for (int i = (14); i <= int(15); i++)
      for (int j = (big); j <= int(m - 1); j++)
        for (size_t o = h[i].find(s[j]); ~o; o = h[i].find(s[j], o + 1))
          ap[i][j]++;
    for (int i = (14); i <= int(15); i++)
      h[i].resize(second), t[i].erase(t[i].begin(), t[i].end() - second);
    for (int i = (16); i <= int(n); i++) {
      for (int j = (big); j <= int(m - 1); j++)
        ap[i][j] = ap[i - 1][j] + ap[i - 2][j];
      for (int j = (big); j <= int(m - 1); j++)
        if (ap[i][j] >= MOD) ap[i][j] -= MOD;
      h[i] = h[i - 1];
      t[i] = t[i - 2];
      merge(t[i - 1], h[i - 2], ap[i]);
    }
    for (int i = (big); i <= int(m - 1); i++) ans[i] = ap[n][i];
  }
}
void sol() {
  sol_big();
  sol_small();
  for (int i = 0; i < int(om); i++) {
    int id = lower_bound(s, s + m, os[i],
                         [&](const string &a, const string &b) {
                           return make_pair(((int)(a).size()), a) >
                                  make_pair(((int)(b).size()), b);
                         }) -
             s;
    PL(ans[id]);
  }
}
int main() {
  read();
  build();
  sol();
  return 0;
}
