#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, F = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') F = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * F;
}
int m, n;
char s[1000 + 5];
int dp[1000 + 5][105][12], ans;
void upd(int &x, int y) {
  x += y;
  if (x > 1000000009) x -= 1000000009;
}
struct AC_automaton {
  int ch[1000 + 5][4], fail[1000 + 5], ed[1000 + 5], tcnt;
  int Cg(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    if (c == 'T') return 3;
  }
  void Insert(char *s) {
    int len = strlen(s + 1), x = 0;
    for (int i = 1; i <= len; i++) {
      int dir = Cg(s[i]);
      if (!ch[x][dir]) ch[x][dir] = ++tcnt;
      x = ch[x][dir];
    }
    ed[x] = max(ed[x], len);
  }
  void Build() {
    queue<int> Q;
    for (int c = 0; c < 4; c++)
      if (ch[0][c]) Q.push(ch[0][c]);
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      ed[x] = max(ed[x], ed[fail[x]]);
      for (int c = 0; c < 4; c++)
        if (ch[x][c]) {
          fail[ch[x][c]] = ch[fail[x]][c];
          Q.push(ch[x][c]);
        } else
          ch[x][c] = ch[fail[x]][c];
    }
  }
  void solve() {
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++)
      for (int j = 0; j <= tcnt; j++)
        for (int k = 0; k <= 10; k++)
          if (dp[i - 1][j][k]) {
            for (int c = 0; c < 4; c++) {
              int p = ch[j][c], nk = ed[p] > k ? 0 : k + 1;
              upd(dp[i][p][nk], dp[i - 1][j][k]);
            }
          }
    for (int j = 0; j <= tcnt; j++) upd(ans, dp[n][j][0]);
    printf("%d\n", ans);
  }
} ac;
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    scanf("%s", s + 1);
    ac.Insert(s);
  }
  ac.Build(), ac.solve();
}
