#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009;
int n, m, tail = 1;
int nxt[110][4], fail[110], ed[110], q[110], dep[110];
long long f[1100][110][15];
char st[15];
inline int mapping(char a) {
  return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3;
}
inline char A(int a) {
  return a == 0 ? 'A' : a == 1 ? 'C' : a == 2 ? 'G' : 'T';
}
inline void checkmax(int &a, int b) { b > a ? a = b : 0; }
void insert() {
  int i, j;
  for (i = 0, j = 0; st[i]; i++) {
    int ch = mapping(st[i]);
    if (!nxt[j][ch]) dep[nxt[j][ch] = tail++] = dep[j] + 1;
    j = nxt[j][ch];
  }
  ed[j] = dep[j];
}
void build() {
  for (int l = 0, r = fail[q[0] = 0] = 0; l <= r; l++) {
    int x = q[l];
    for (int i = 0; i < 4; i++)
      if (!nxt[x][i])
        nxt[x][i] = nxt[fail[x]][i];
      else
        checkmax(ed[nxt[x][i]],
                 ed[fail[q[++r] = nxt[x][i]] = (x ? nxt[fail[x]][i] : 0)]);
  }
}
long long dp(int i, int j, int k) {
  if (~f[i][j][k]) return f[i][j][k];
  if (!i) return f[i][j][k] = (ed[j] >= k);
  f[i][j][k] = 0;
  for (int p = 0; p < 4; p++)
    if (nxt[j][p]) {
      int nk = (ed[j] >= k ? 1 : k + 1);
      if (dep[nxt[j][p]] < nk) continue;
      f[i][j][k] += dp(i - 1, nxt[j][p], nk);
    }
  return f[i][j][k] %= MOD;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%s", st), insert();
  build();
  memset(f, 0xff, sizeof(f));
  cout << dp(n, 0, 0) << endl;
  return 0;
}
