#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool checkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool checkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int MOD = 1000000009;
struct AhoCorasick {
  static const int MAXN = 128;
  static const int CHARSET = 4;
  int cnt, mark[MAXN], fail[MAXN];
  int trie[MAXN][CHARSET];
  void init() {
    mark[0] = 0;
    fill(trie[0], trie[0] + CHARSET, -1);
    cnt = 1;
  }
  void insert(const int s[], int len) {
    int p = 0;
    for (int i = 0; i < len; ++i) {
      if (trie[p][s[i]] == -1) {
        mark[cnt] = 0;
        fill(trie[cnt], trie[cnt] + CHARSET, -1);
        trie[p][s[i]] = cnt++;
      }
      p = trie[p][s[i]];
    }
    mark[p] = len;
  }
  queue<int> bfs;
  void build() {
    fail[0] = 0;
    for (int i = 0; i < CHARSET; ++i) {
      if (trie[0][i] != -1) {
        fail[trie[0][i]] = 0;
        bfs.push(trie[0][i]);
      } else
        trie[0][i] = 0;
    }
    while (!bfs.empty()) {
      int p = bfs.front();
      bfs.pop();
      mark[p] = max(mark[p], mark[fail[p]]);
      for (int i = 0; i < CHARSET; ++i) {
        if (trie[p][i] != -1) {
          fail[trie[p][i]] = trie[fail[p]][i];
          bfs.push(trie[p][i]);
        } else
          trie[p][i] = trie[fail[p]][i];
      }
    }
  }
} ac;
const int MAXLEN = 12;
int dp[1024][AhoCorasick::MAXN][MAXLEN];
const char pat[] = "ATCG";
int s[256];
char buf[256];
int main() {
  int N, M;
  while (scanf("%d%d", &N, &M) != EOF) {
    ac.init();
    for (int i = 0; i < (M); ++i) {
      scanf("%s", buf);
      int len = strlen(buf);
      for (int j = 0; j < (len); ++j) {
        s[j] = strchr(pat, buf[j]) - pat;
      }
      ac.insert(s, len);
    }
    ac.build();
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 0; i < (N); ++i) {
      for (int node = 0; node < (ac.cnt); ++node) {
        for (int len = 0; len < (MAXLEN); ++len) {
          if (dp[i][node][len] == 0) continue;
          for (int j = 0; j < (4); ++j) {
            if (ac.mark[ac.trie[node][j]] > len) {
              dp[i + 1][ac.trie[node][j]][0] += dp[i][node][len];
              dp[i + 1][ac.trie[node][j]][0] %= MOD;
            } else if (len + 1 < MAXLEN) {
              dp[i + 1][ac.trie[node][j]][len + 1] += dp[i][node][len];
              dp[i + 1][ac.trie[node][j]][len + 1] %= MOD;
            }
          }
        }
      }
    }
    int ans = 0;
    for (int node = 0; node < (ac.cnt); ++node) {
      ans += dp[N][node][0];
      ans %= MOD;
    }
    printf("%d\n", ans);
  }
  return 0;
}
