#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  const static int N = 4;
  int n, m;
  long long v[N][N];
  void init(int _n, int _m) {
    n = _n;
    m = _m;
    for (int i = (0); i < (n); i++)
      for (int j = (0); j < (m); j++) v[i][j] = 0;
  }
  void init(int _n) { init(_n, _n); }
  void ident() {
    for (int i = (0); i < (n); i++)
      for (int j = (0); j < (n); j++) v[i][j] = 0;
    for (int i = (0); i < (n); i++) v[i][i] = 1;
  }
  Matrix operator*(const Matrix &o) const {
    assert(m == o.n);
    Matrix res;
    res.init(n, o.m);
    long long mod2 = 1000000007 * 1ll * 1000000007;
    for (int i = (0); i < (n); i++)
      for (int j = (0); j < (o.m); j++) {
        for (int k = (0); k < (m); k++) {
          res.v[i][j] += v[i][k] * o.v[k][j];
          if (res.v[i][j] >= mod2) res.v[i][j] -= mod2;
        }
        res.v[i][j] %= 1000000007;
      }
    return res;
  }
  Matrix operator^(long long k) {
    Matrix res;
    res.init(n);
    res.ident();
    Matrix a = *this;
    while (k) {
      if (k & 1) res = res * a;
      a = a * a;
      k /= 2;
    }
    return res;
  }
};
long long k;
int sl[100005];
char s[100005];
int n;
int tre[100005][2];
int trc[100005][2];
bool as[2];
int ne[100005], nc[100005];
int go() {
  n = int(strlen(s));
  sl[0] = 0;
  for (int i = (1); i < (n + 1); i++) {
    int v = s[i - 1] - 'a', j;
    for (j = sl[i - 1]; j && s[j] != 'a' + v; j = sl[j])
      ;
    if (j + 1 != i && s[j] == 'a' + v)
      sl[i] = j + 1;
    else
      sl[i] = 0;
  }
  for (int i = (0); i < (n); i++) {
    int v = s[i] - 'a';
    if (i == n - 1) {
      tre[i][v] = sl[n];
      trc[i][v] = 1;
    } else {
      tre[i][v] = i + 1;
      trc[i][v] = 0;
    }
    v = !v;
    trc[i][v] = 0;
    if (i == 0) {
      tre[i][v] = 0;
    } else {
      tre[i][v] = tre[sl[i]][v];
    }
  }
  for (int i = (0); i < (2); i++) as[i] = false;
  for (int i = (2); i < (k + 1); i++) {
    as[i & 1] = true;
    for (int j = (0); j < (n); j++) {
      ne[j] = tre[tre[j][~i & 1]][i & 1];
      if (j && ne[j] != ne[j - 1]) as[i & 1] = false;
    }
    for (int j = (0); j < (n); j++) {
      nc[j] = trc[j][~i & 1] + trc[tre[j][~i & 1]][i & 1];
      if (nc[j] >= 1000000007) nc[j] -= 1000000007;
    }
    for (int j = (0); j < (n); j++) tre[j][i & 1] = ne[j];
    for (int j = (0); j < (n); j++) trc[j][i & 1] = nc[j];
    if (as[0] && as[1]) {
      int a = tre[0][~i & 1];
      int b = tre[0][i & 1];
      Matrix m1;
      m1.init(4);
      for (int j = (0); j < (2); j++) m1.v[(0 * 2 + j)][(1 * 2 + j)] = 1;
      for (int j = (0); j < (2); j++)
        m1.v[(1 * 2 + j)][(1 * 2 + j)] = 1, m1.v[(1 * 2 + j)][(0 * 2 + 1)] = 1;
      Matrix m2;
      m2.init(4);
      for (int j = (0); j < (2); j++) m2.v[(0 * 2 + j)][(1 * 2 + j)] = 1;
      for (int j = (0); j < (2); j++)
        m2.v[(1 * 2 + j)][(1 * 2 + j)] = 1, m2.v[(1 * 2 + j)][(0 * 2 + 0)] = 1;
      Matrix t = (m2 * m1) ^ ((k - i) / 2);
      if ((k - i) & 1) t = m1 * t;
      Matrix im;
      im.init(4, 1);
      for (int j = (0); j < (2); j++) {
        im.v[(j * 2 + 0)][0] = trc[a][(i & 1) ^ j ^ 1];
        im.v[(j * 2 + 1)][0] = trc[b][(i & 1) ^ j ^ 1];
      }
      im = t * im;
      return (trc[0][i & 1] + im.v[(1 * 2 + 0)][0] - trc[a][i & 1] +
              1000000007) %
             1000000007;
    }
  }
  return trc[0][k & 1];
}
int main() {
  int m;
  scanf("%lld%d", &k, &m);
  k--;
  for (int Z = (0); Z < (m); Z++) {
    scanf(" %s", s);
    printf("%d\n", go());
  }
}
