#include <bits/stdc++.h>
using namespace std;
const int maxn = 1003, maxm = 13, maxl = 13, mod = 1000000009;
char s[maxl];
int tr[maxm * maxl][4], fail[maxm * maxl], en[maxm * maxl], cnt, n, m,
    dp[maxn][maxm * maxl][maxl];
int gt(char c) { return c == 'A' ? 0 : (c == 'C' ? 1 : (c == 'G' ? 2 : 3)); }
void PlusEqual(int &x, int y) {
  if ((x += y) >= mod) x -= mod;
}
void insert(const char *s) {
  int p = 0, i;
  for (i = 0; s[i]; i++) {
    if (tr[p][gt(s[i])] == 0) tr[p][gt(s[i])] = ++cnt;
    p = tr[p][gt(s[i])];
  }
  en[p] = i;
}
void build() {
  queue<int> q;
  for (int i = 0; i < 4; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (!q.empty()) {
    int p = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
      if (tr[p][i])
        fail[tr[p][i]] = tr[fail[p]][i], q.push(tr[p][i]),
        en[tr[p][i]] = max(en[tr[p][i]], en[fail[tr[p][i]]]);
      else
        tr[p][i] = tr[fail[p]][i];
    }
  }
}
void query() {
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int p = 0; p <= cnt; p++) {
      for (int j = 0; j < 4; j++) {
        int q = tr[p][j];
        for (int k = 0; k <= 10; k++) {
          if (en[q] >= k + 1)
            PlusEqual(dp[i + 1][q][0], dp[i][p][k]);
          else
            PlusEqual(dp[i + 1][q][k + 1], dp[i][p][k]);
        }
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%s", s), insert(s);
  build();
  query();
  int ans = 0;
  for (int i = 0; i <= cnt; i++)
    if (en[i]) PlusEqual(ans, dp[n][i][0]);
  printf("%d\n", ans);
  return 0;
}
