#include <bits/stdc++.h>
using namespace std;
int dp[1010][101];
int w[101][101][11];
int fail[110];
int ch[101][4], cnt;
int yin[1100], is[1010], len[101];
void ins(char *s) {
  int t = 0, l = 0;
  for (int i = 0; s[i]; i++) {
    l++;
    int c = yin[s[i]];
    if (!ch[t][c]) ch[t][c] = ++cnt;
    t = ch[t][c];
    len[t] = l;
  }
  len[t] = strlen(s);
  is[t] = max(is[t], len[t]);
}
queue<int> q;
void AC() {
  int i, j, u, v;
  for (i = 0; i < 4; i++)
    if (ch[0][i]) q.push(ch[0][i]);
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (i = 0; i < 4; i++)
      if (ch[u][i]) {
        v = ch[u][i];
        fail[v] = ch[fail[u]][i];
        q.push(v);
        is[v] = max(is[v], is[fail[v]]);
      } else
        ch[u][i] = ch[fail[u]][i];
  }
}
void dfs(int ori, int sta, int ci) {
  if (len[sta] < ci) return;
  if (is[sta] && ci && is[sta] >= ci)
    w[ori][sta][ci] = 1;
  else {
    for (int i = 0; i < 4; i++) dfs(ori, ch[sta][i], ci + 1);
  }
}
char s[110];
int main() {
  int n, i, j, k, m;
  yin['A'] = 0;
  yin['C'] = 1;
  yin['G'] = 2;
  yin['T'] = 3;
  scanf("%d%d", &n, &m);
  while (m--) {
    scanf("%s", s);
    ins(s);
  }
  AC();
  for (i = 0; i <= cnt; i++) dfs(i, i, 0);
  dp[0][0] = 1;
  int mod = 1000000009;
  for (i = 0; i < n; i++)
    for (j = 0; j <= cnt; j++)
      if (dp[i][j]) {
        for (k = 1; k <= 10; k++)
          if (i + k <= n)
            for (int ii = 1; ii <= cnt; ii++)
              if (w[j][ii][k]) {
                dp[i + k][ii] += dp[i][j];
                dp[i + k][ii] %= mod;
              }
      }
  int ans = 0;
  for (i = 0; i <= cnt; i++) ans = (ans + dp[n][i]) % mod;
  printf("%d\n", ans);
}
