#include <bits/stdc++.h>
using namespace std;
const int maxn = 105, maxk = 4, maxl = 12, mod = 1000000009, maxm = 1005;
int n, m, tot, ans, maxlen;
int chd[maxn][maxk], fail[maxn], f[maxm][maxl][maxn], dep[maxn], len[maxn];
class Query {
 private:
  int q[101];
  int l, r;

 public:
  Query() { l = 0, r = -1; }
  void push(int x) { q[++r] = x; }
  int front() { return q[l]; }
  void pop() { l++; }
  void clear() { l = 0, r = -1; }
  bool empty() { return l > r; }
  int size() { return r - l + 1; }
} q;
char s[101];
inline int get(char c) {
  return c == 'A' ? 0 : (c == 'C' ? 1 : (c == 'G' ? 2 : 3));
}
inline int strlen(char* s) {
  for (int i = 0;; i++) {
    if (s[i] == 0) return i;
  }
}
inline void memset(char* s) {
  for (int i = 0;; i++) {
    if (s[i])
      s[i] = 0;
    else
      break;
  }
}
void insert(char* s) {
  int now = 1;
  int so = strlen(s);
  for (int i = 0; i < so; now = chd[now][get(s[i])], i++)
    if (chd[now][get(s[i])] == 0)
      chd[now][get(s[i])] = ++tot, dep[tot] = dep[now] + 1;
  len[now] = dep[now];
}
void getfail() {
  while (!q.empty()) q.pop();
  for (int i = 0; i <= 3; i++) {
    if (chd[1][i]) {
      q.push(chd[1][i]);
      fail[chd[1][i]] = 1;
    } else
      chd[1][i] = 1;
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i <= 3; i++) {
      if (chd[x][i]) {
        q.push(chd[x][i]);
        fail[chd[x][i]] = chd[fail[x]][i];
      } else {
        chd[x][i] = chd[fail[x]][i];
      }
    }
    len[x] = len[x] > len[fail[x]] ? len[x] : len[fail[x]];
  }
}
int main() {
  tot = 1;
  scanf("%d %d", &m, &n);
  for (int i = 1; i <= n; i++) {
    memset(s);
    scanf("%s", s);
    maxlen = maxlen > strlen(s) ? maxlen : strlen(s);
    insert(s);
  }
  getfail();
  f[0][0][1] = 1;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j <= maxlen; j++) {
      for (int k = 1; k <= tot; k++) {
        if (f[i][j][k]) {
          for (int p = 0; p <= 3; p++) {
            int x = chd[k][p];
            if (len[x] > j) {
              f[i + 1][0][x] = (f[i + 1][0][x] + f[i][j][k]) % mod;
            } else {
              f[i + 1][j + 1][x] = (f[i + 1][j + 1][x] + f[i][j][k]) % mod;
            }
          }
        }
      }
    }
  }
  for (int i = 1; i <= tot; i++) {
    ans = (ans + f[m][0][i]) % mod;
  }
  printf("%d\n", ans);
  return 0;
}
