#include <bits/stdc++.h>
using namespace std;
struct node {
  int maxl;
  node *fail, *next[4];
} nd[10 * 10 + 5];
node *ncnt, *root;
vector<node *> vec;
int n, m;
int typ[200], dp1[10 * 10 + 5][10 * 10 + 5][10 + 5],
    dp2[1000 + 5][10 + 5][10 * 10 + 5];
int go[10 * 10 + 5][4];
char str[10 + 5];
void Init() {
  ncnt = root = &nd[0];
  root->maxl = 0;
  root->fail = NULL;
  memset(root->next, 0, sizeof(root->next));
}
inline node *NewNode() {
  node *p = ++ncnt;
  p->maxl = 0;
  p->fail = NULL;
  memset(p->next, 0, sizeof(p->next));
  return p;
}
void Insert(char *s, node *rt) {
  node *p = rt, *q;
  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    int j = typ[(int)s[i]];
    q = p->next[j];
    if (q == NULL) {
      q = NewNode();
      p->next[j] = q;
    }
    p = q;
  }
  p->maxl = max(p->maxl, len);
}
void ACBuild(node *rt) {
  queue<node *> que;
  for (int i = 0; i < 4; i++)
    if (rt->next[i]) {
      rt->next[i]->fail = rt;
      que.push(rt->next[i]);
    }
  node *p, *bef;
  while (que.empty() == false) {
    p = que.front();
    que.pop();
    for (int i = 0; i < 4; i++) {
      if (p->next[i]) {
        for (bef = p->fail; bef; bef = bef->fail)
          if (bef->next[i]) {
            p->next[i]->fail = bef->next[i];
            break;
          }
        if (bef == NULL)
          p->next[i]->fail = rt;
        else
          p->next[i]->maxl = max(p->next[i]->maxl, p->next[i]->fail->maxl);
        que.push(p->next[i]);
      }
    }
  }
}
void ACPrepare() {
  node *q;
  for (node *p = root; p <= ncnt; p++) {
    for (int i = 0; i < 4; i++) {
      if (p->next[i])
        go[p - nd][i] = p->next[i] - nd;
      else {
        q = p;
        while (q->next[i] == NULL && q != root) q = q->fail;
        q = q->next[i];
        if (q == NULL)
          go[p - nd][i] = root - nd;
        else
          go[p - nd][i] = q - nd;
      }
    }
  }
}
int DP2() {
  dp2[0][0][0] = 1;
  for (int i = 1; i <= n; i++)
    for (node *p = root; p <= ncnt; p++) {
      for (int k = 0; k < 4; k++) {
        for (int j1 = 0; j1 < nd[go[p - nd][k]].maxl; j1++)
          dp2[i][0][go[p - nd][k]] =
              (1LL * dp2[i][0][go[p - nd][k]] + 1LL * dp2[i - 1][j1][p - nd]) %
              1000000009;
        for (int j1 = nd[go[p - nd][k]].maxl; j1 < 10; j1++)
          dp2[i][j1 + 1][go[p - nd][k]] = (1LL * dp2[i][j1 + 1][go[p - nd][k]] +
                                           1LL * dp2[i - 1][j1][p - nd]) %
                                          1000000009;
      }
    }
  int ret = 0;
  for (node *p = root; p <= ncnt; p++)
    ret = (1LL * ret + 1LL * dp2[n][0][p - nd]) % 1000000009;
  return ret;
}
int main() {
  Init();
  typ['A'] = 0, typ['C'] = 1, typ['G'] = 2, typ['T'] = 3;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%s", str);
    Insert(str, root);
  }
  ACBuild(root);
  ACPrepare();
  int ans = DP2();
  printf("%d\n", ans);
  return 0;
}
