#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 = 1e5 + 5;
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;
vector<int> odr;
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();
      odr.push_back(pt - Node::mem);
      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];
          }
      }
    }
    reverse((odr).begin(), (odr).end());
  }
} ac;
const int MOD = 1e9 + 7;
const int i2 = MOD - MOD / 2;
inline int add(const int &a, const int &b) {
  return a + b < MOD ? a + b : a + b - MOD;
}
inline int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sig;
int dp[maxn];
void find_occur(const string &s, int ans[]) {
  memset(dp, 0, sizeof(int) * sig);
  Node *pt = ac.root;
  for (char c : s) {
    pt = pt->to[c - 'a'];
    dp[pt - Node::mem]++;
  }
  for (int i : odr)
    dp[Node::mem[i].fail - Node::mem] =
        add(dp[Node::mem[i].fail - Node::mem], dp[i]);
  for (int i = 0; i < int(sig); i++)
    if (~Node::mem[i].who) ans[Node::mem[i].who] = dp[i];
}
long long n;
int 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;
  }
}
string os[maxn];
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;
  for (int i = 0; i < int(m); i++) ac.add(s[i], i);
  ac.build();
  sig = Node::pmem - Node::mem;
}
array<array<int, 3>, 3> operator*(const array<array<int, 3>, 3> &a,
                                  const array<array<int, 3>, 3> &b) {
  array<array<int, 3>, 3> ret;
  for (int i = 0; i < int(3); i++)
    for (int j = 0; j < int(3); j++) ret[i][j] = 0;
  for (int i = 0; i < int(3); i++)
    for (int j = 0; j < int(3); j++)
      for (int k = 0; k < int(3); k++)
        ret[i][k] = add(ret[i][k], mul(a[i][j], b[j][k]));
  return ret;
}
int ans[maxn];
string f[maxn];
void sol_small() {
  f[1] = "a";
  f[2] = "b";
  for (int i = (3); i <= int(26); i++) f[i] = f[i - 1] + f[i - 2];
  if (n <= 26) {
    find_occur(f[n], ans);
  } else {
    static int tmp[4][maxn];
    for (int i = (27); i <= int(29); i++) f[i] = f[i - 1] + f[i - 2];
    for (int i = 0; i < int(4); i++) find_occur(f[i + 26], tmp[i]);
    array<array<int, 3>, 3> X, A;
    X[0][0] = 0;
    X[0][1] = 0;
    X[0][2] = 1;
    X[1][0] = 1;
    X[1][1] = 0;
    X[1][2] = 2;
    X[2][0] = 0;
    X[2][1] = 1;
    X[2][2] = 0;
    A[0][0] = 1;
    A[0][1] = 0;
    A[0][2] = 0;
    A[1][0] = 0;
    A[1][1] = 1;
    A[1][2] = 0;
    A[2][0] = 0;
    A[2][1] = 0;
    A[2][2] = 1;
    for (long long b = n - 26; b; b >>= 1, X = X * X)
      if (b & 1) A = A * X;
    for (int i = 0; i < int(m); i++) {
      int dlt = tmp[3][i];
      dlt = add(dlt, MOD - tmp[1][i]);
      dlt = add(dlt, MOD - tmp[1][i]);
      dlt = add(dlt, MOD - tmp[0][i]);
      dlt = mul(dlt, i2);
      int a[] = {tmp[0][i], tmp[1][i], tmp[2][i]};
      for (int j = 0; j < int(3); j++) a[j] = add(a[j], dlt);
      int res = 0;
      for (int j = 0; j < int(3); j++) res = add(res, mul(a[j], A[j][0]));
      res = add(res, MOD - dlt);
      ans[i] = res;
    }
  }
}
void sol() {
  sol_small();
  for (int i = 0; i < int(om); i++) {
    Node *pt = ac.root;
    for (char c : os[i]) pt = pt->to[c - 'a'];
    PL(ans[pt->who]);
  }
}
int main() {
  read();
  build();
  sol();
  return 0;
}
