#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
const int M = 110;
const int CD = 4;
int fail[M];
int Q[M];
int ch[M][CD];
int ID[128];
int val[M];
int sz;
int flag[M];
void Init() {
  fail[0] = 0;
  memset(ch[0], 0, sizeof(ch[0]));
  sz = 1;
  ID['A'] = 0;
  ID['T'] = 1;
  ID['G'] = 2;
  ID['C'] = 3;
}
void Insert(char *s, int len) {
  int p = 0;
  for (; *s; s++) {
    int c = ID[*s];
    if (!ch[p][c]) {
      memset(ch[sz], 0, sizeof(ch[sz]));
      val[sz] = 0;
      flag[sz] = 0;
      ch[p][c] = sz++;
    }
    p = ch[p][c];
  }
  val[p] = len;
  flag[p] = 1;
}
void Construct() {
  int *s = Q, *e = Q;
  for (int i = 0; i < CD; i++) {
    if (ch[0][i]) {
      fail[ch[0][i]] = 0;
      *e++ = ch[0][i];
    }
  }
  while (s != e) {
    int u = *s++;
    for (int i = 0; i < CD; i++) {
      int &v = ch[u][i];
      if (v) {
        *e++ = v;
        fail[v] = ch[fail[u]][i];
        val[v] = max(val[v], val[fail[v]]);
        flag[v] |= flag[fail[v]];
      } else {
        v = ch[fail[u]][i];
      }
    }
  }
}
int dp[1010][110][15];
char s[20];
int main() {
  int n, m;
  Init();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%s", s);
    int len = strlen(s);
    Insert(s, len);
  }
  Construct();
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (int len = 0; len < n; len++) {
    for (int i = 0; i < sz; i++) {
      for (int k = 0; k < 10; k++) {
        for (int j = 0; j < CD; j++) {
          int nxt = ch[i][j];
          int kk = k + 1;
          if (flag[nxt]) {
            if (val[nxt] >= kk) {
              kk = 0;
            }
          }
          dp[len + 1][nxt][kk] += dp[len][i][k];
          dp[len + 1][nxt][kk] %= mod;
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < sz; i++) {
    ans = (ans + dp[n][i][0]) % mod;
  }
  printf("%d\n", ans);
  return 0;
}
