#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MOD = 1e9 + 9;
int idx(char c) {
  if (c == 'A') return 0;
  if (c == 'T') return 1;
  if (c == 'G') return 2;
  if (c == 'C') return 3;
  assert(0);
  return -1;
}
const int _ = 120;
int tag[_];
namespace ACAM {
const int _ = 120;
int tr[_][4], fail[_], tot = 0;
void insert(char* S) {
  int u = 0, len = 0;
  for (int i = 0; S[i]; i++) {
    int ex = idx(S[i]);
    if (!tr[u][ex]) tr[u][ex] = ++tot;
    u = tr[u][ex];
    len++;
  }
  assert(tag[u] <= len);
  tag[u] = len;
}
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 now = Q.front();
    Q.pop();
    for (int i = 0; i < 4; i++) {
      if (tr[now][i]) {
        fail[tr[now][i]] = tr[fail[now]][i], Q.push(tr[now][i]);
      } else
        tr[now][i] = tr[fail[now]][i];
    }
    tag[now] = max(tag[now], tag[fail[now]]);
  }
}
}  // namespace ACAM
int dp[1010][120][12];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    static char S[_];
    scanf("%s", S);
    ACAM::insert(S);
  }
  ACAM::build();
  int KK = ACAM::tot;
  dp[0][0][0] = 1;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= KK; j++) {
      for (int k = 0; k <= 10; k++) {
        int now = dp[i][j][k];
        for (int t = 0; t < 4; t++) {
          int ex = ACAM::tr[j][t];
          if (k < tag[ex])
            (dp[i + 1][ex][0] += now) %= MOD;
          else
            (dp[i + 1][ex][k + 1] += now) %= MOD;
        }
      }
    }
  }
  int ret = 0;
  for (int i = 1; i <= KK; i++) {
    (ret += dp[n][i][0]) %= MOD;
  }
  printf("%d\n", ret);
  return 0;
}
