#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
const int maxm = 305;
const int mod = 1e9 + 9;
int n, m;
int id[55];
int dp[1005][maxn][12];
struct AC {
  int cnt;
  int tr[maxn][30], fail[maxn];
  int val[maxn];
  queue<int> q;
  void init() {
    cnt = 0;
    memset(tr, 0, sizeof(tr));
    memset(fail, 0, sizeof(fail));
    memset(val, 0, sizeof(val));
    while (!q.empty()) q.pop();
  }
  void insert(char *s) {
    int u = 0;
    int len = strlen(s);
    for (int i = 0; i <= len - 1; i++) {
      int x = id[s[i] - 'A'];
      if (!tr[u][x]) tr[u][x] = ++cnt;
      u = tr[u][x];
    }
    val[u] = len;
  }
  void build() {
    for (int i = 0; i <= 3; i++)
      if (tr[0][i]) q.push(tr[0][i]);
    while (q.size()) {
      int u = q.front();
      q.pop();
      val[u] = max(val[u], val[fail[u]]);
      for (int i = 0; i <= 3; i++) {
        if (tr[u][i])
          fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
        else
          tr[u][i] = tr[fail[u]][i];
      }
    }
  }
  void solve() {
    dp[0][0][0] = 1;
    for (int i = 0; i <= n - 1; i++)
      for (int j = 0; j <= cnt; j++)
        for (int p = 0; p <= 10; p++)
          for (int k = 0; k <= 3; k++) {
            int nxt = tr[j][k];
            if (val[nxt] >= p + 1)
              dp[i + 1][nxt][0] += dp[i][j][p], dp[i + 1][nxt][0] %= mod;
            else
              dp[i + 1][nxt][p + 1] += dp[i][j][p],
                  dp[i + 1][nxt][p + 1] %= mod;
          }
    int ans = 0;
    for (int j = 0; j <= cnt; j++) ans += dp[n][j][0], ans %= mod;
    printf("%d\n", ans);
  }
} ac;
char s[15];
int main() {
  id['A' - 'A'] = 0;
  id['C' - 'A'] = 1;
  id['G' - 'A'] = 2;
  id['T' - 'A'] = 3;
  scanf("%d%d", &n, &m);
  ac.init();
  for (int i = 1; i <= m; i++) scanf("%s", s), ac.insert(s);
  ac.build();
  ac.solve();
  return 0;
}
