#include <bits/stdc++.h>
using namespace std;
int k;
int sl[10005];
char s[10005];
int n;
int tre[10005][2];
int trc[10005][2];
bool as[2];
int ne[10005], nc[10005];
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;
  if (k <= 1) return trc[0][k];
  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];
  }
  return trc[0][k & 1];
}
int main() {
  int m;
  scanf("%d%d", &k, &m);
  k--;
  for (int Z = (0); Z < (m); Z++) {
    scanf(" %s", s);
    printf("%d\n", go());
  }
}
