#include <bits/stdc++.h>
using namespace std;
int tn, ch[111][4], fail[111], flag[111];
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 d[1111][111][11];
bool vis[1111][111][11];
int main() {
  idx['A'] = 0;
  idx['C'] = 1;
  idx['G'] = 2;
  idx['T'] = 3;
  char str[11];
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%s", str);
    insert(str, strlen(str));
  }
  getFail();
  d[0][0][0] = 1;
  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] %= 1000000009;
        if (!vis[len + 1][ch[x][i]][0]) {
          vis[len + 1][ch[x][i]][0] = 1;
          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] %= 1000000009;
        if (!vis[len + 1][ch[x][i]][k + 1]) {
          vis[len + 1][ch[x][i]][k + 1] = 1;
          que.push(Node(len + 1, ch[x][i], k + 1));
        }
      }
    }
    vis[len][x][k] = 0;
  }
  int res = 0;
  for (int i = 0; i <= tn; ++i) {
    res += d[n][i][0];
    res %= 1000000009;
  }
  printf("%d", res);
  return 0;
}
