#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline int Chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline int Chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline T read() {
  T sum = 0, fl = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fl = -1;
  for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
  return sum * fl;
}
inline void proc_status() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>())
       << endl;
}
const int Maxn = 1000 + 5, Maxm = 10 + 5;
const int Mod = 1000000009;
int N, M;
namespace AC {
struct info {
  int ch[4], fail, maxlen, dp[Maxn][Maxm];
  info() { memset(dp, -1, sizeof dp); }
} node[Maxm * Maxm];
int node_cnt;
inline void insert(char *S, int n) {
  int o = 0;
  for (int i = 1; i <= n; ++i) {
    int c = S[i] - 'A';
    if (!node[o].ch[c]) node[o].ch[c] = ++node_cnt;
    o = node[o].ch[c];
  }
  Chkmax(node[o].maxlen, n);
}
inline void build_fail() {
  static queue<int> Q;
  for (int c = 0; c < 4; ++c)
    if (node[0].ch[c]) Q.push(node[0].ch[c]);
  while (!Q.empty()) {
    int first = Q.front();
    Q.pop();
    Chkmax(node[first].maxlen, node[node[first].fail].maxlen);
    for (int c = 0; c < 4; ++c) {
      int &second = node[first].ch[c];
      if (second) {
        node[second].fail = node[node[first].fail].ch[c];
        Q.push(second);
      } else
        second = node[node[first].fail].ch[c];
    }
  }
}
inline int get_dp(int pos, int first, int len) {
  if (len > 10) return 0;
  if (pos == N + 1) {
    if (!len)
      return 1;
    else
      return 0;
  }
  int &ans = node[first].dp[pos][len];
  if (~ans) return ans;
  ans = 0;
  for (int c = 0; c < 4; ++c) {
    int second = node[first].ch[c];
    if (node[second].maxlen >= len + 1)
      (ans += get_dp(pos + 1, second, 0)) %= Mod;
    else
      (ans += get_dp(pos + 1, second, len + 1)) %= Mod;
  }
  return ans;
}
inline void work() {
  build_fail();
  printf("%d\n", get_dp(1, 0, 0));
}
}  // namespace AC
inline void Solve() { AC ::work(); }
inline void Input() {
  N = read<int>(), M = read<int>();
  for (int i = 1; i <= M; ++i) {
    static char S[Maxm];
    scanf("%s", S + 1);
    int n = strlen(S + 1);
    for (int j = 1; j <= n; ++j)
      if (S[j] == 'A')
        S[j] = 'A';
      else if (S[j] == 'C')
        S[j] = 'B';
      else if (S[j] == 'G')
        S[j] = 'C';
      else
        S[j] = 'D';
    AC ::insert(S, n);
  }
}
int main() {
  Input();
  Solve();
  return 0;
}
