#include <bits/stdc++.h>
const int MM = 500005;
const int M1 = 4;
const int mod = 1000000009;
int N, M;
char str[1005];
int tr[350];
int flag[5];
int len[25];
int L;
int q[MM], front, last;
struct node {
  int sign;
  int fail;
  int next[4];
} tree[MM];
void init(int p) {
  for (int i = 0; i < M1; i++) tree[p].next[i] = 0;
  tree[p].sign = tree[p].fail = 0;
}
void insert(char s[], int id) {
  int i = 0, p = 0, x;
  while (s[i]) {
    x = tr[s[i]];
    flag[x] = 1;
    if (tree[p].next[x] == 0) {
      tree[p].next[x] = ++L;
      init(L);
    }
    p = tree[p].next[x];
    i++;
  }
  tree[p].sign = id;
}
void build() {
  front = last = 0;
  for (int i = 0; i < M1; i++)
    if (tree[0].next[i]) {
      q[front++] = tree[0].next[i];
      tree[tree[0].next[i]].fail = 0;
    }
  while (last < front) {
    int t = q[last++];
    for (int i = 0; i < M1; ++i) {
      int tt = tree[t].next[i];
      int ff = tree[t].fail;
      if (tree[t].next[i]) {
        if (tree[t].sign == 0) {
          tree[t].sign = tree[ff].sign;
        }
        tree[tt].fail = tree[ff].next[i];
        q[front++] = tt;
      } else
        tree[t].next[i] = tree[ff].next[i];
    }
  }
}
int dp[1050][105][12];
int Gao() {
  int i, j, k, t;
  int ret = 0;
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (i = 0; i < N; i++) {
    for (j = 0; j <= L; j++) {
      for (k = 0; k <= 10; k++) {
        if (!dp[i][j][k]) continue;
        for (t = 0; t < 4; t++) {
          int tmp = tree[j].next[t];
          if (tree[tmp].sign && len[tree[tmp].sign] > k)
            dp[i + 1][tmp][0] = (dp[i + 1][tmp][0] + dp[i][j][k]) % mod;
          else
            dp[i + 1][tmp][k + 1] = (dp[i + 1][tmp][k + 1] + dp[i][j][k]) % mod;
        }
      }
    }
  }
  for (i = 0; i <= L; i++) {
    ret = (ret + dp[N][i][0]) % mod;
  }
  return ret;
}
int main() {
  tr['A'] = 0;
  tr['C'] = 1;
  tr['G'] = 2;
  tr['T'] = 3;
  scanf("%d%d", &N, &M);
  L = 0;
  init(0);
  memset(len, 0, sizeof(len));
  memset(flag, 0, sizeof(flag));
  for (int i = 1; i <= M; i++) {
    scanf("%s", str);
    len[i] = strlen(str);
    insert(str, i);
  }
  build();
  printf("%d\n", Gao());
  return 0;
}
