#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int N = 1e6 + 10;
string s[101];
string x;
long long dp[101];
long long n;
int m;
int fail[N];
struct matrix {
  long long v[4][4];
  matrix() {
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) v[i][j] = 0;
  }
  matrix(long long u[4][4]) {
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) v[i][j] = u[i][j];
  }
  matrix operator*(const matrix a) const {
    matrix ans;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++)
        for (int k = 0; k < 4; k++) {
          ans.v[i][j] += (v[i][k] * a.v[k][j]);
          ans.v[i][j] = (ans.v[i][j] + mod) % mod;
        }
    return ans;
  }
  void setunit() {
    for (int i = 0; i < 4; i++) v[i][i] = 1;
  }
};
long long mtx[4][4] = {
    {1, 2, -1, -1},
    {1, 0, 0, 0},
    {0, 1, 0, 0},
    {0, 0, 1, 0},
};
matrix calc(long long i) {
  matrix tmp(mtx);
  matrix ans;
  ans.setunit();
  while (i) {
    if (i & 1ll) ans = tmp * ans;
    tmp = tmp * tmp;
    i = i / 2ll;
  }
  return ans;
}
long long kmp(int p) {
  int m = x.length(), n = s[p].length();
  if (m > n) return 0;
  for (int i = 1, j = fail[0] = -1; i < m; i++) {
    while (j >= 0 && x[j + 1] != x[i]) j = fail[j];
    if (x[j + 1] == x[i]) j++;
    fail[i] = j;
  }
  int ans = 0;
  for (int i = 0, j = -1; i < n; i++) {
    while (j >= 0 && x[j + 1] != s[p][i]) j = fail[j];
    if (x[j + 1] == s[p][i]) j++;
    if (j == m - 1) {
      ans++;
      j = fail[j];
    }
  }
  return (long long)ans;
}
long long calc(int a, int b) {
  string p = s[a] + s[b];
  int s1 = s[a].length();
  int m = x.length(), n = p.length();
  if (m > n) return 0;
  for (int i = 1, j = fail[0] = -1; i < m; i++) {
    while (j >= 0 && x[j + 1] != x[i]) j = fail[j];
    if (x[j + 1] == x[i]) j++;
    fail[i] = j;
  }
  int ans = 0;
  for (int i = 0, j = -1; i < n; i++) {
    while (j >= 0 && x[j + 1] != p[i]) j = fail[j];
    if (x[j + 1] == p[i]) j++;
    if (j == m - 1) {
      if ((i - m + 1 < s1) && (i + 1) > s1) ans++;
      j = fail[j];
    }
  }
  return (long long)ans;
}
int main() {
  s[1] = "a";
  s[2] = "b";
  for (int i = 3; i <= 30; i++) s[i] = s[i - 1] + s[i - 2];
  cin >> n >> m;
  while (m--) {
    cin >> x;
    if (n <= 25) {
      cout << kmp((int)n) << endl;
      continue;
    }
    int len = x.length();
    int r = 1;
    while (s[r].length() < len) r++;
    long long add1 = calc(r, r), add2 = calc(r + 1, r);
    for (int i = 1; i <= r + 2; i++) dp[i] = kmp(i);
    dp[r + 3] = dp[r + 2] + dp[r + 1] + add1;
    dp[r + 4] = dp[r + 3] + dp[r + 2] + add2;
    dp[r + 5] = dp[r + 4] + dp[r + 3] + add1;
    dp[r + 6] = dp[r + 5] + dp[r + 4] + add2;
    if (n <= r + 6) {
      cout << dp[n] << endl;
      continue;
    }
    matrix mat = calc(n - r - 6);
    long long ans = 0;
    for (int i = 0; i < 4; i++) ans += mat.v[0][i] * dp[r + 6 - i];
    ans = ans % mod;
    while (ans < 0) ans += mod;
    cout << ans << endl;
  }
}
