#include <bits/stdc++.h>
using namespace std;
struct KMP {
  vector<int> d;
  string s;
  KMP(string _s = "") {
    s = _s;
    d.assign(s.size(), 0);
    d[0] = -1;
    int cur = -1;
    for (int i = 1; i < s.size(); i++) {
      while (cur > -1 && s[i] != s[cur + 1]) cur = d[cur];
      d[i] = s[i] == s[cur + 1] ? ++cur : -1;
    }
  }
  vector<int> getPattern(string &_s) {
    vector<int> p;
    int cur = -1;
    for (int i = 0; i < _s.size(); i++) {
      if (cur + 1 == s.size()) cur = d[cur];
      while (cur > -1 && _s[i] != s[cur + 1]) cur = d[cur];
      p.push_back(_s[i] == s[cur + 1] ? ++cur : -1);
    }
    return p;
  }
};
struct Matrix {
  vector<vector<int> > a;
  int r, c;
  Matrix(int _r = 0, int _c = 0) {
    r = _r;
    c = _c;
    a.assign(r, vector<int>(c, 0));
  }
  friend Matrix operator*(const Matrix &b, const Matrix &c) {
    Matrix ans(b.r, c.c);
    for (int i = 0; i < b.r; i++)
      for (int j = 0; j < c.c; j++)
        for (int k = 0; k < c.r; k++) {
          ans.a[i][j] += 1ll * b.a[i][k] * c.a[k][j] % 1000000007;
          ans.a[i][j] %= 1000000007;
        }
    return ans;
  }
  void print() {
    printf("Printing Matrix\n");
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        printf("%d ", a[i][j]);
      }
      printf("\n");
    }
  }
};
Matrix b[200];
string f[100], s;
int get(string &t, KMP &tmp) {
  int cnt = 0;
  vector<int> a = tmp.getPattern(t);
  for (int j = 0; j < a.size(); j++)
    if (a[j] + 1 == s.size()) cnt++;
  return cnt;
}
int solve(long long int k) {
  vector<int> t(100, 0);
  int m[5];
  KMP tmp = KMP(s);
  f[1] = "a";
  t[1] = get(f[1], tmp);
  f[2] = "b";
  t[2] = get(f[2], tmp);
  int i2;
  for (int i = 3;; i++) {
    if (f[i].size() == 0) f[i] = f[i - 1] + f[i - 2];
    t[i] = get(f[i], tmp);
    if (f[i].size() >= s.size()) {
      i2 = i;
      break;
    }
  }
  for (int i = i2 + 1; i <= i2 + 4; i++) {
    if (f[i].size() == 0) f[i] = f[i - 1] + f[i - 2];
    int cnt = 0;
    vector<int> a = tmp.getPattern(f[i]);
    for (int j = 0; j < a.size(); j++)
      if (a[j] + 1 == s.size()) cnt++;
    t[i] = cnt;
    if (i > i2 + 1) m[i % 2] = t[i] - t[i - 1] - t[i - 2];
  }
  if (k <= i2 + 5) {
    return t[k];
  } else {
    Matrix a(1, 4);
    Matrix ans = b[0];
    a.a[0][0] = m[0];
    a.a[0][1] = m[1];
    a.a[0][2] = t[i2 + (i2 & 1)];
    a.a[0][3] = t[i2 + 1 + (i2 & 1)];
    long long int newK = (k - i2 - (i2 & 1)) / 2;
    int i = 1;
    while (newK) {
      if (newK & 1) ans = ans * b[i];
      i++;
      newK >>= 1;
    }
    a = a * ans;
    if (k & 1)
      return a.a[0][3];
    else
      return a.a[0][2];
  }
}
int main() {
  long long int k, m;
  ios_base::sync_with_stdio(0);
  int B[4][4] = {{1, 0, 1, 1}, {0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 1, 2}};
  b[0] = Matrix(4, 4);
  b[1] = Matrix(4, 4);
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) b[1].a[i][j] = B[i][j], b[0].a[i][i] = 1;
  for (int i = 2; i < 70; i++) {
    b[i] = b[i - 1] * b[i - 1];
  }
  cin >> k >> m;
  for (int i = 1; i <= m; i++) {
    cin >> s;
    cout << solve(k) << '\n';
  }
}
