#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const long long mod = 1e9 + 7;
struct Matrix {
  int n, m;
  long long a[10][10];
  Matrix() { memset(this->a, 0, sizeof(this->a)); }
  Matrix(int n, int m) {
    this->n = n;
    this->m = m;
    memset(this->a, 0, sizeof(this->a));
  }
};
Matrix operator*(Matrix a, Matrix b) {
  Matrix out = Matrix(a.n, b.m);
  for (int i = 0; i < a.n; i++) {
    for (int j = 0; j < b.m; j++) {
      for (int p = 0; p < a.m; p++) {
        out.a[i][j] = (out.a[i][j] + a.a[i][p] * b.a[p][j]) % mod;
      }
    }
  }
  return out;
}
Matrix fastPow(Matrix x, long long p) {
  Matrix answer = Matrix(x.n, x.m), current = x;
  for (int i = 0; i < x.n; i++) {
    answer.a[i][i] = 1;
  }
  while (p != 0) {
    if (p % 2 != 0) {
      answer = answer * current;
    }
    p /= 2;
    current = current * current;
  }
  return answer;
}
string fString[35];
void precalcStrings() {
  fString[1] = "a";
  fString[2] = "b";
  for (int i = 3; i <= 30; i++) {
    fString[i] = fString[i - 1] + fString[i - 2];
  }
}
int match(string s, string pattern) {
  vector<int> f;
  f.assign(pattern.size() + 1, 0);
  int len = 0;
  f[0] = 0;
  for (int i = 1; i < pattern.size(); i++) {
    if (pattern[len] == pattern[i]) {
      len++;
      f[i] = len;
    } else {
      while (pattern[len] != pattern[i] && len != 0) len = f[len - 1];
      if (pattern[len] == pattern[i]) {
        len++;
        f[i] = len;
      } else {
        f[i] = 0;
      }
    }
  }
  len = 0;
  int answer = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == pattern[len]) {
      len++;
      if (len == pattern.size()) {
        answer++;
        len = f[pattern.size() - 1];
      }
    } else {
      while (s[i] != pattern[len] && len != 0) len = f[len - 1];
      if (s[i] == pattern[len]) {
        len++;
      } else {
        len = 0;
      }
    }
  }
  return answer;
}
string getPrefix(string s, int len) {
  string out = "";
  for (int i = 0; i < len; i++) out += s[i];
  return out;
}
string getSuffix(string s, int len) {
  string out = "";
  for (int i = s.size() - len; i < s.size(); i++) out += s[i];
  return out;
}
long long k;
string s;
int val[2];
string prefix;
string suffix[2];
long long dp[MAXN];
void solve() {
  if (k < 30) {
    cout << match(fString[k], s) << '\n';
    return;
  }
  int n = s.size();
  int ind;
  for (int i = 1; i < 30; i++) {
    if (fString[i].size() > s.size()) {
      ind = i;
      break;
    }
  }
  prefix = getPrefix(fString[ind], n - 1);
  suffix[0] = getSuffix(fString[ind], n - 1);
  suffix[1] = getSuffix(fString[ind + 1], n - 1);
  val[0] = match(suffix[0] + prefix, s);
  val[1] = match(suffix[1] + prefix, s);
  Matrix A = Matrix(1, 4);
  A.a[0][0] = match(fString[ind], s);
  A.a[0][1] = match(fString[ind + 1], s);
  A.a[0][2] = val[1];
  A.a[0][3] = val[0];
  Matrix B = Matrix(4, 4);
  B.a[0][0] = 0;
  B.a[0][1] = 1;
  B.a[0][2] = 0;
  B.a[0][3] = 0;
  B.a[1][0] = 1;
  B.a[1][1] = 1;
  B.a[1][2] = 0;
  B.a[1][3] = 0;
  B.a[2][0] = 0;
  B.a[2][1] = 1;
  B.a[2][2] = 0;
  B.a[2][3] = 1;
  B.a[3][0] = 0;
  B.a[3][1] = 0;
  B.a[3][2] = 1;
  B.a[3][3] = 0;
  cout << (A * fastPow(B, k - ind - 1)).a[0][1] << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  precalcStrings();
  int T;
  cin >> k >> T;
  while (T--) {
    cin >> s;
    solve();
  }
}
