#include <bits/stdc++.h>
const int mod = 1e9 + 9;
using namespace std;
namespace Trie {
int nxt[1010][4], fail[1010];
int end[10010], tot, root, id[300];
int dp[1001][101][12], mx[1001];
int newnode() {
  for (int i = 0; i < 4; i++) nxt[tot][i] = -1;
  fail[tot] = end[tot] = mx[tot] = 0;
  return tot++;
}
void init() {
  id['A'] = 0, id['G'] = 1, id['C'] = 2;
  id['T'] = 3;
  tot = 0;
  root = newnode();
}
int idx(char now) { return id[now]; }
void insert(char s[], int tp) {
  int p = root, len = strlen(s);
  for (int i = 0; s[i]; i++) {
    if (nxt[p][idx(s[i])] == -1) nxt[p][idx(s[i])] = newnode();
    p = nxt[p][idx(s[i])];
  }
  mx[p] = max(mx[p], len);
}
void build() {
  queue<int> que;
  que.push(root);
  while (!que.empty()) {
    int p = que.front();
    que.pop();
    end[p] = end[fail[p]];
    mx[p] = max(mx[fail[p]], mx[p]);
    for (int i = 0; i < 4; i++) {
      if (~nxt[p][i]) {
        if (p == root)
          fail[nxt[p][i]] = root;
        else
          fail[nxt[p][i]] = nxt[fail[p]][i];
        que.push(nxt[p][i]);
      } else {
        if (p == root)
          nxt[p][i] = root;
        else
          nxt[p][i] = nxt[fail[p]][i];
      }
    }
  }
}
void add(int &a, int b) { a = a + b >= mod ? a + b - mod : a + b; }
int query(int n, int m) {
  dp[0][root][0] = 1;
  for (int _ = 0; _ < n; _++) {
    for (int i = 0; i < tot; i++) {
      for (int len = 0; len <= 10; len++) {
        if (!dp[_][i][len]) continue;
        for (int j = 0; j < 4; j++) {
          if (mx[nxt[i][j]] >= len + 1)
            add(dp[_ + 1][nxt[i][j]][0], dp[_][i][len]);
          else
            add(dp[_ + 1][nxt[i][j]][len + 1], dp[_][i][len]);
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < tot; i++) add(ans, dp[n][i][0]);
  return ans;
}
};  // namespace Trie
char s[20];
int main(int argc, char const *argv[]) {
  int n, m;
  scanf("%d%d", &n, &m);
  Trie::init();
  for (int i = 0; i < m; i++) scanf("%s", s), Trie::insert(s, i);
  Trie::build();
  printf("%d\n", Trie::query(n, m));
  return 0;
}
