#include <bits/stdc++.h>
using namespace std;
const int N = 2055, C = 4, L = 205, M = 2050;
const int INF = 1e9;
const int mod = 1e9 + 9;
int idx[128];
struct node {
  int ch[C], fail;
  int cnt;
} a[N];
int tcnt;
int n, m;
int val[N];
void Re0() {
  memset(a, 0, sizeof a);
  tcnt = 0;
}
void Insert(char *s, int id) {
  int p = 0;
  int n = strlen(s);
  for (int j = 0; j < n; j++) {
    int i = idx[s[j]];
    if (!a[p].ch[i]) {
      a[p].ch[i] = ++tcnt;
    }
    p = a[p].ch[i];
  }
  val[p] = n;
}
void Build() {
  queue<int> Q;
  for (int i = 0; i < C; i++)
    if (a[0].ch[i]) Q.push(a[0].ch[i]);
  while (!Q.empty()) {
    int p = Q.front();
    Q.pop();
    for (int i = 0; i < C; i++) {
      int &q = a[p].ch[i], r = a[p].fail;
      if (q) {
        Q.push(q);
        while (r && !a[r].ch[i]) r = a[r].fail;
        a[q].fail = a[r].ch[i];
      } else
        q = a[r].ch[i];
      val[q] = max(val[q], val[a[q].fail]);
    }
  }
}
int d[1005][105][15];
int dp() {
  memset(d, 0, sizeof d);
  d[0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= tcnt; j++) {
      for (int k = 0; k <= 10; k++)
        for (int c = 0; c < C; c++) {
          int t = a[j].ch[c];
          if (val[t] >= k + 1)
            d[i + 1][t][0] = (d[i + 1][t][0] + d[i][j][k]) % mod;
          else
            d[i + 1][t][k + 1] = (d[i + 1][t][k + 1] + d[i][j][k]) % mod;
        }
    }
  }
  int ans = 0;
  for (int i = 0; i <= tcnt; i++) ans = (ans + d[n][i][0]) % mod;
  return ans;
}
char s[L];
int main() {
  idx['A'] = 0, idx['G'] = 1, idx['C'] = 2, idx['T'] = 3;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%s", s);
    Insert(s, i);
  }
  Build();
  int ans = dp();
  printf("%d\n", ans);
}
