#include <bits/stdc++.h>
using namespace std;
const int MAXX = 1000100;
void multiply(long long A[2][2], long long B[2][2], long long q) {
  long long C[2][2];
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      C[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        C[i][j] += A[i][k] * B[k][j];
        C[i][j] %= q;
      }
    }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) A[i][j] = C[i][j];
}
long long fib(long long n, long long q) {
  if (n < 0) return 0;
  long long F[2][2] = {{1, 1}, {1, 0}};
  long long I[2][2] = {{1, 0}, {0, 1}};
  long long k = 1;
  while (k <= n) {
    if (k & n) multiply(I, F, q);
    multiply(F, F, q);
    k *= 2;
  }
  return (int)(I[0][0] % q);
}
vector<vector<bool> > back(vector<bool>& T) {
  vector<bool> v;
  int i;
  for (i = 0; i < T.size() - 1; i++) {
    if (T[i] == 0 && T[i + 1] == 1) {
      v.push_back(0);
      i++;
    } else if (T[i] == 0)
      v.push_back(1);
    else
      v.push_back(0);
  }
  if (i < T.size()) {
    vector<bool> v1 = v;
    v.push_back(0);
    v1.push_back(1);
    vector<vector<bool> > V;
    V.push_back(v1);
    V.push_back(v);
    return V;
  } else {
    vector<vector<bool> > V;
    V.push_back(v);
    return V;
  }
}
inline bool valid(vector<bool>& T) {
  int a = 0, b = 0;
  for (int i = 0; i < T.size(); i++) {
    if (T[i] == 0) {
      a++;
      b = 0;
    } else {
      b++;
      a = 0;
    }
    if (a >= 3 || b >= 2) return false;
  }
  return true;
}
long long count(vector<bool>& T, long long n, long long q) {
  if (!valid(T)) return 0;
  if (T.size() > 2 || (T.size() == 2 && T[0] != T[1])) {
    vector<vector<bool> > v = back(T);
    long long s = 0;
    for (int i = 0; i < v.size(); i++) {
      s += count(v[i], n - 1, q);
      s %= q;
    }
    return s;
  } else {
    if (T.size() == 1) {
      if (T[0] == 0)
        return fib(n - 1, q);
      else
        return fib(n - 2, q) + (n == 0 ? 1 : 0);
    } else {
      if (T[0] == 1 && T[1] == 1)
        return 0;
      else if (T[0] == 0 && T[1] == 0)
        return fib(n - 3, q) - (n % 2 == 1 ? 1 : 0);
    }
  }
}
void readString(vector<bool>& s) {
  s.clear();
  char c;
  while (true) {
    c = getchar();
    if (c != 'a' && c != 'b') break;
    s.push_back(c == 'b');
  }
}
int main() {
  int z;
  long long n;
  scanf("%I64d %d", &n, &z);
  long long q = 1000000000 + 7;
  getchar();
  while (z--) {
    vector<bool> V;
    readString(V);
    for (int i = 0; i < V.size(); i++) V[i] = V[i] ? false : true;
    long long ccc;
    printf("%I64d\n", (ccc = count(V, n - 1, q)) < 0 ? 0 : ccc);
  }
  return 0;
}
