#include <bits/stdc++.h>
const int MAXN = 1e6 + 10, MAXM = 1e4 + 10, MOD = 1e9 + 7;
struct Matrix {
  int m[3][3];
  Matrix(int v = 0) {
    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j) m[i][j] = v;
  }
  inline void E() { m[0][0] = m[1][1] = m[2][2] = 1; }
  inline void gao(int fuck) {
    m[0][0] = 0, m[0][1] = 1, m[0][2] = 0;
    m[1][0] = 1, m[1][1] = 1, m[1][2] = 0;
    m[2][0] = 0, m[2][1] = fuck, m[2][2] = 1;
  }
  inline int *operator[](int x) { return m[x]; }
  inline const int *operator[](const int &x) const { return m[x]; }
  inline friend Matrix operator*(const Matrix &A, const Matrix &B) {
    Matrix C(0);
    for (int k = 0; k < 3; ++k)
      for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
          C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
    return C;
  }
  inline friend Matrix operator^(Matrix A, long long k) {
    Matrix ans;
    ans.E();
    for (; k; A = A * A, k >>= 1)
      if (k & 1) ans = ans * A;
    return ans;
  }
};
std::string s1 = "a", s2 = "b", s3 = "ba", s4 = "bab";
int fail[MAXN];
char S[MAXN], T[MAXN];
inline int match(std::string s, std::string t) {
  int n = s.size(), m = t.size();
  for (int i = 1; i <= n; ++i) S[i] = s[i - 1];
  for (int i = 1; i <= m; ++i) T[i] = t[i - 1];
  fail[0] = fail[1] = 0;
  for (int i = 2, j = 0; i <= m; ++i) {
    while (j && T[i] != T[j + 1]) j = fail[j];
    if (T[i] == T[j + 1]) ++j;
    fail[i] = j;
  }
  int ans = 0;
  for (int i = 1, j = 0; i <= n; ++i) {
    while (j && S[i] != T[j + 1]) j = fail[j];
    if (S[i] == T[j + 1]) ++j;
    if (j == m) ++ans, j = fail[j];
  }
  return ans;
}
struct String {
  int id, ans, sz;
  std::string s;
} s[MAXM];
int m;
long long n;
inline bool cmpS(const String &a, const String &b) {
  return a.sz == b.sz ? a.s < b.s : a.sz < b.sz;
}
inline bool cmpId(const String &a, const String &b) { return a.id < b.id; }
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cout.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    std::cin >> s[i].s;
    s[i].sz = s[i].s.size();
    s[i].id = i;
  }
  std::sort(s + 1, s + m + 1, cmpS);
  for (int i = 1, now = 1; i <= m; ++i) {
    while (now < n && (int)s1.size() < (int)s[i].s.size()) {
      ++now;
      s1 = s4 + s3;
      std::swap(s1, s2);
      std::swap(s2, s3);
      std::swap(s3, s4);
    }
    if (now == n) {
      s[i].ans = match(s1, s[i].s);
      continue;
    }
    int t1 = match(s1, s[i].s), t2 = match(s2, s[i].s), t3 = match(s3, s[i].s),
        t4 = match(s4, s[i].s);
    int d1 = t3 - t1 - t2, d2 = t4 - t2 - t3;
    Matrix m1, m2, p(0);
    m1.gao(d1);
    m2.gao(d2);
    p[0][0] = t1, p[0][1] = t2, p[0][2] = 1;
    p = p * ((m1 * m2) ^ ((n - now) / 2));
    if ((n - now) & 1) p = p * m1;
    s[i].ans = p[0][0];
  }
  std::sort(s + 1, s + m + 1, cmpId);
  for (int i = 1; i <= m; ++i) printf("%d\n", s[i].ans);
  return 0;
}
