#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  char ch = getchar();
  bool f = false;
  while (!isdigit(ch)) {
    if (ch == '-') {
      f = true;
    }
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  x = f ? -x : x;
  return;
}
template <typename T>
inline void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 ^ 48);
  return;
}
const int N = 1e3 + 5, M = 205, W = 11, MOD = 1e9 + 9;
int tn, ch[M][4], fail[M], flag[M];
int idx[128];
void insert(char *s, int k) {
  int x = 0;
  for (int i = 0; s[i]; i++) {
    int y = idx[s[i]];
    if (ch[x][y] == 0) ch[x][y] = ++tn;
    x = ch[x][y];
  }
  flag[x] = k;
}
void getFail() {
  queue<int> que;
  for (int i = 0; i < 4; i++)
    if (ch[0][i]) que.push(ch[0][i]);
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    for (int i = 0; i < 4; i++) {
      if (ch[x][i]) {
        que.push(ch[x][i]);
        fail[ch[x][i]] = ch[fail[x]][i];
        flag[ch[x][i]] = max(flag[ch[x][i]], flag[ch[fail[x]][i]]);
      } else
        ch[x][i] = ch[fail[x]][i];
    }
  }
}
struct Node {
  int len, x, k;
  Node(int _l = 0, int _x = 0, int _k = 0) : len(_l), x(_x), k(_k) {}
};
int n, m;
int d[N][M][W];
bool vis[N][M][W];
char str[W];
int main() {
  idx['A'] = 0, idx['C'] = 1, idx['G'] = 2, idx['T'] = 3;
  read(n), read(m);
  for (int i = 0; i < m; i++) {
    scanf("%s", str);
    insert(str, strlen(str));
  }
  getFail();
  d[0][0][0] = vis[0][0][0] = 1;
  queue<Node> que;
  que.push(Node(0, 0, 0));
  while (!que.empty()) {
    Node nd = que.front();
    que.pop();
    int len = nd.len, x = nd.x, k = nd.k;
    if (len == n) continue;
    for (int i = 0; i < 4; i++) {
      if (k + 1 <= flag[ch[x][i]]) {
        d[len + 1][ch[x][i]][0] =
            (d[len][x][k] + d[len + 1][ch[x][i]][0] >= MOD
                 ? d[len][x][k] + d[len + 1][ch[x][i]][0] - MOD
                 : d[len][x][k] + d[len + 1][ch[x][i]][0]);
        if (!vis[len + 1][ch[x][i]][0])
          vis[len + 1][ch[x][i]][0] = true,
                    que.push(Node(len + 1, ch[x][i], 0));
      } else {
        if (k >= 9) continue;
        d[len + 1][ch[x][i]][k + 1] =
            (d[len][x][k] + d[len + 1][ch[x][i]][k + 1] >= MOD
                 ? d[len][x][k] + d[len + 1][ch[x][i]][k + 1] - MOD
                 : d[len][x][k] + d[len + 1][ch[x][i]][k + 1]);
        if (!vis[len + 1][ch[x][i]][k + 1])
          vis[len + 1][ch[x][i]][k + 1] = true,
                                     que.push(Node(len + 1, ch[x][i], k + 1));
      }
    }
  }
  int res = 0;
  for (int i = 0; i <= tn; i++)
    res = (res + d[n][i][0] >= MOD ? res + d[n][i][0] - MOD : res + d[n][i][0]);
  write(res);
  return 0;
}
