#include <bits/stdc++.h>
using namespace std;
template <typename T>
void get_int(T &x) {
  char t = getchar();
  bool neg = false;
  x = 0;
  for (; (t > '9' || t < '0') && t != '-'; t = getchar())
    ;
  if (t == '-') neg = true, t = getchar();
  for (; t <= '9' && t >= '0'; t = getchar()) x = x * 10 + t - '0';
  if (neg) x = -x;
}
template <typename T>
void print_int(T x) {
  if (x < 0) putchar('-'), x = -x;
  short a[20] = {}, sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const double pi = acos(-1.0);
const int maxn = 1111;
const int mod = 1e9 + 9;
int ch[maxn][4], fail[maxn], root, tot, mx[maxn], q[maxn];
void clear() {
  root = 1;
  for (int i = 0; i < 4; i++) ch[0][i] = 1;
  tot = 1;
}
char s[20];
void addstr() {
  scanf("%s", s);
  int cur = root, t, i;
  for (i = 0; s[i]; i++) {
    if (s[i] == 'A')
      t = 0;
    else if (s[i] == 'C')
      t = 1;
    else if (s[i] == 'G')
      t = 2;
    else
      t = 3;
    if (!ch[cur][t]) ch[cur][t] = ++tot;
    cur = ch[cur][t];
  }
  mx[cur] = i;
}
void build() {
  int rear = 1;
  q[0] = root;
  for (int _ = 0, i; _ < rear; _++) {
    i = q[_];
    for (int k = 0; k < 4; k++) {
      if (ch[i][k]) {
        int &f = fail[ch[i][k]];
        f = fail[i];
        while (f && !ch[f][k]) f = fail[f];
        f = ch[f][k];
        q[rear++] = ch[i][k];
        if (mx[f] && !mx[ch[i][k]]) mx[ch[i][k]] = mx[f];
      } else
        ch[i][k] = ch[fail[i]][k];
    }
  }
}
int n, m, f[233][15], g[233][15];
int main() {
  clear();
  get_int(n), get_int(m);
  for (int i = 0; i < m; i++) addstr();
  build();
  f[root][0] = 1;
  for (int _ = 1; _ <= n; _++) {
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= tot; i++)
      for (int k = 0; k < 4; k++)
        for (int j = 1; j <= 10; j++) {
          g[ch[i][k]][j] += f[i][j - 1];
          if (g[ch[i][k]][j] >= mod) g[ch[i][k]][j] -= mod;
        }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= tot; i++) {
      if (mx[i] > 0) {
        for (int j = 1; j <= 10; j++) {
          if (j <= mx[i]) {
            f[i][0] += g[i][j];
            if (f[i][0] >= mod) f[i][0] -= mod;
          } else {
            f[i][j] += g[i][j];
            if (f[i][j] >= mod) f[i][j] -= mod;
          }
        }
      } else
        memcpy(f[i], g[i], sizeof(f[i]));
    }
  }
  int ans = 0;
  for (int i = 1; i <= tot; i++)
    if (mx[i]) {
      ans += f[i][0];
      if (ans >= mod) ans -= mod;
    }
  printf("%d\n", ans);
  return 0;
}
