#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
long long read() {
  long long s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
long long cnt = 0;
struct trie {
  long long ch[26];
  long long fail;
  long long tail;
} t[10010];
long long f(char c) {
  if (c == 'A') return 0;
  if (c == 'C') return 1;
  if (c == 'T')
    return 2;
  else
    return 3;
}
void insert(string s) {
  long long l = s.size();
  long long nw = 0;
  for (long long i = 0, iend = l - 1; i <= iend; ++i) {
    if (t[nw].ch[f(s[i])] == 0) {
      t[nw].ch[f(s[i])] = ++cnt;
    }
    nw = t[nw].ch[f(s[i])];
  }
  t[nw].tail = l;
}
void bfs() {
  queue<long long> q;
  for (long long i = 0, iend = 25; i <= iend; ++i) {
    if (t[0].ch[i]) {
      t[t[0].ch[i]].fail = 0;
      q.push(t[0].ch[i]);
    }
  }
  while (!q.empty()) {
    long long nw = q.front();
    q.pop();
    for (long long i = 0, iend = 25; i <= iend; ++i) {
      if (t[nw].ch[i] != 0) {
        t[t[nw].ch[i]].fail = t[t[nw].fail].ch[i];
        t[t[nw].ch[i]].tail =
            max(t[t[nw].ch[i]].tail, t[t[t[nw].ch[i]].fail].tail);
        q.push(t[nw].ch[i]);
      } else {
        t[nw].ch[i] = t[t[nw].fail].ch[i];
      }
    }
  }
}
const long long inf = 1e16;
long long dp[1010][1010][11];
const long long mod = 1e9 + 9;
signed main() {
  n = read(), m = read();
  long long l = 0;
  for (long long i = 1, iend = m; i <= iend; ++i) {
    string s;
    cin >> s;
    long long ss = s.size();
    l = max(l, ss);
    insert(s);
  }
  bfs();
  dp[0][0][0] = 1;
  for (long long i = 0, iend = n - 1; i <= iend; ++i) {
    for (long long j = 0, jend = cnt; j <= jend; ++j) {
      long long v;
      for (long long k = 0, kend = l; k <= kend; ++k) {
        v = dp[i][j][k];
        if (v) {
          for (long long p = 0, pend = 3; p <= pend; ++p) {
            long long nw = t[j].ch[p];
            if (t[nw].tail > k)
              (dp[i + 1][nw][0] += v) %= mod;
            else if (k < l)
              (dp[i + 1][nw][k + 1] += v) %= mod;
          }
        }
      }
    }
  }
  long long ans = 0;
  for (long long i = 0, iend = cnt; i <= iend; ++i) {
    (ans += dp[n][i][0]) %= mod;
  }
  cout << ans;
}
