#include <bits/stdc++.h>
using namespace std;
const int MAXF = 30;
const long long MOD = 1000000007;
struct Mat {
  long long a[3][3];
  Mat operator*(Mat b) {
    Mat ret;
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
        ret.a[i][j] = 0;
        for (int k = 0; k < 3; k++) ret.a[i][j] += a[i][k] * b.a[k][j];
        ret.a[i][j] %= MOD;
      }
    }
    return ret;
  }
};
long long K;
int M;
string s;
string fib[MAXF], fz[MAXF];
Mat I;
void init() {
  fib[1] = "a";
  fib[2] = "b";
  for (int i = 3; i < MAXF; i++) fib[i] = fib[i - 1] + fib[i - 2];
  for (int i = 1; i < MAXF; i++) fz[i] = fib[i] + fib[i];
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) I.a[i][j] = (i == j);
}
int app_num(string &f) {
  int N = s.size(), first = f.size();
  int ans = 0;
  for (int i = 0; i <= first - N; i++) {
    bool ok = true;
    for (int j = 0; j < N; j++) {
      if (s[j] != f[i + j]) {
        ok = false;
        break;
      }
    }
    if (ok) ans++;
  }
  return ans;
}
int calc() {
  if (K <= 2) return s == fib[K];
  int N = s.size();
  int first = 2;
  while (N > (int)fib[first].size()) first++;
  if (K < first) return 0;
  long long b0 = app_num(fib[first]), b1 = app_num(fib[first + 1]),
            b2 = app_num(fib[first + 2]), b3 = app_num(fz[first]);
  long long d1 = b2 - b0 - b1, d2 = b3 - 2 * b0;
  long long diff = K - first;
  long long dq = diff >> 1;
  Mat C, A;
  C = I;
  A.a[2][0] = A.a[2][1] = 0;
  A.a[0][0] = A.a[0][1] = A.a[1][0] = A.a[2][2] = 1;
  A.a[1][1] = 2;
  A.a[0][2] = d1;
  A.a[1][2] = d1 + d2;
  while (dq) {
    if (dq & 1LL) C = C * A;
    A = A * A;
    dq >>= 1;
  }
  if (diff & 1LL)
    return (b0 * C.a[1][0] + b1 * C.a[1][1] + C.a[1][2]) % MOD;
  else
    return (b0 * C.a[0][0] + b1 * C.a[0][1] + C.a[0][2]) % MOD;
}
int main() {
  init();
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> K >> M;
  for (int i = 0; i < M; i++) {
    cin >> s;
    int ans = calc();
    cout << ans << "\n";
  }
  return 0;
}
