#include <bits/stdc++.h>
using namespace std;
struct Trie {
  int len, id;
  Trie *nxt[4], *fail;
} buf[120], *Q[120], *root;
int top, idx[300], dp[1200][110][15];
char w[120];
void insert(Trie *tr, char *w, int len) {
  if (*w == 0) {
    tr->len = len;
    return;
  }
  int i = idx[*w];
  if (!tr->nxt[i]) {
    tr->nxt[i] = &buf[top];
    buf[top].id = top;
    memset(buf[top].nxt, 0, sizeof(buf[top].nxt));
    buf[top++].len = 0;
  }
  insert(tr->nxt[i], w + 1, len + 1);
}
void bfs() {
  int f = 0, r = 0;
  Q[r++] = root;
  while (f < r) {
    Trie *p, *s;
    for (int i = 0; i < 4; i++) {
      p = Q[f];
      s = p->nxt[i];
      if (s) {
        Q[r++] = s;
        p = p->fail;
        while (!p->nxt[i]) p = p->fail;
        s->fail = p->nxt[i];
        s->len = max(s->len, s->fail->len);
      } else
        p->nxt[i] = p->fail->nxt[i];
    }
    f++;
  }
}
void pre() {
  idx['A'] = 0;
  idx['T'] = 1;
  idx['C'] = 2;
  idx['G'] = 3;
  root = &buf[0];
  root->fail = &buf[119];
  root->id = 0;
  root->len = 0;
  for (int i = 0; i < 4; i++) root->fail->nxt[i] = root;
}
void add(int &a, int b) {
  a += b;
  if (a >= 1000000009) a -= 1000000009;
}
int main() {
  int n, m;
  pre();
  while (scanf("%d%d", &n, &m) == 2) {
    memset(root->nxt, 0, sizeof(root->nxt));
    top = 1;
    for (int i = 0; i < m; i++) {
      scanf("%s", w);
      insert(root, w, 0);
    }
    bfs();
    for (int i = 0; i <= n; i++)
      for (int j = 0; j < top; j++)
        for (int k = 0; k < 11; k++) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < top; j++)
        for (int k = 0; k < 11; k++) {
          if (dp[i][j][k] == 0) continue;
          for (int s = 0; s < 4; s++) {
            Trie *p = buf[j].nxt[s];
            int m = k + 1;
            if (p->len >= m) m = 0;
            add(dp[i + 1][p->id][m], dp[i][j][k]);
          }
        }
    int ans = 0;
    for (int i = 0; i < top; i++) {
      add(ans, dp[n][i][0]);
    }
    printf("%d\n", ans);
  }
}
