#include <bits/stdc++.h>
using namespace std;
int qmax(int &x, int y) {
  if (x < y) x = y;
}
int qmin(int &x, int y) {
  if (x > y) x = y;
}
inline int read() {
  char s;
  int k = 0, base = 1;
  while ((s = getchar()) != '-' && s != EOF && !(isdigit(s)))
    ;
  if (s == EOF) exit(0);
  if (s == '-') base = -1, s = getchar();
  while (isdigit(s)) {
    k = k * 10 + (s ^ '0');
    s = getchar();
  }
  return k * base;
}
void write(int x) {
  if (x < 0) {
    putchar('-');
    write(-x);
  } else {
    if (x / 10) write(x / 10);
    putchar(x % 10 + '0');
  }
}
int Map[100], n, m, id;
struct node {
  int end, fail;
} a[150];
char ch[150][5];
int val[150];
int son[150][5];
char Ch[20];
void insert() {
  int now = 0, len = strlen(Ch + 1);
  for (int i = 1; i <= len; i++) {
    if (ch[now][Map[Ch[i]]] == 0) {
      ch[now][Map[Ch[i]]] = ++id;
      son[now][Map[Ch[i]]] = id;
    }
    now = ch[now][Map[Ch[i]]];
  }
  a[now].end++;
  val[now] = len;
}
void get_fail() {
  queue<int> q;
  while (!q.empty()) q.pop();
  for (int i = 1; i <= 4; i++)
    if (ch[0][i] != 0) q.push(ch[0][i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 1; i <= 4; i++) {
      if (ch[u][i] != 0) {
        a[ch[u][i]].fail = ch[a[u].fail][i];
        qmax(val[ch[u][i]], val[a[ch[u][i]].fail]);
        q.push(ch[u][i]);
      } else
        ch[u][i] = ch[a[u].fail][i];
    }
  }
}
int dp[1500][160][12];
int mod = 1e9 + 9;
int ans;
int main() {
  Map['A'] = 1;
  Map['C'] = 2;
  Map['G'] = 3;
  Map['T'] = 4;
  n = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    scanf("%s", Ch + 1);
    insert();
  }
  get_fail();
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= id; j++)
      for (int k = 0; k <= 10; k++)
        if (dp[i][j][k] != 0) {
          int v;
          for (int c = 1; c <= 4; c++) {
            v = ch[j][c];
            if (val[v] >= k + 1) {
              dp[i + 1][v][0] += dp[i][j][k];
              if (dp[i + 1][v][0] >= mod) dp[i + 1][v][0] -= mod;
            } else {
              dp[i + 1][v][k + 1] += dp[i][j][k];
              if (dp[i + 1][v][k + 1] >= mod) dp[i + 1][v][k + 1] -= mod;
            }
          }
        }
  }
  for (int i = 0; i <= id; i++) {
    ans += dp[n][i][0];
    ans = ans >= mod ? ans -= mod : ans;
  }
  printf("%d\n", ans);
  return 0;
}
