#include <bits/stdc++.h>
#pragma comment(linker, "/stack:100000000")
using namespace std;
const int MOD = 1000000009;
vector<string> s;
set<string> pr;
vector<string> P;
int nxt[101][4];
int fs[101][4];
int dp[2][101][1001];
char get(char c) {
  switch (c) {
    case 'A':
      return '0';
    case 'C':
      return '1';
    case 'G':
      return '2';
    case 'T':
      return '3';
    default:
      return 0;
  }
}
bool endsWith(string s, string t) {
  if ((int)(s).size() < (int)(t).size()) return false;
  for (int i = (int)(s).size() - (int)(t).size(), j = 0; i < (int)(s).size();
       i++, j++) {
    if (s[i] != t[j]) return false;
  }
  return true;
}
int main() {
  int n, m;
  cin >> n >> m;
  s.resize(m);
  for (int(i) = 0; (i) < (m); (i)++) {
    cin >> s[i];
    for (int(j) = 0; (j) < ((int)(s[i]).size()); (j)++) s[i][j] = get(s[i][j]);
  }
  pr.insert("");
  for (int(i) = 0; (i) < ((int)(s).size()); (i)++) {
    string t;
    for (int(j) = 0; (j) < ((int)(s[i]).size()); (j)++) {
      t += s[i][j];
      pr.insert(t);
    }
  }
  P = vector<string>((pr).begin(), (pr).end());
  int M = (int)(P).size();
  for (int(i) = 0; (i) < (M); (i)++) {
    string str = P[i];
    for (char c = '0'; c <= '3'; c++) {
      string t = str + c;
      int id = -1;
      for (int(j) = 0; (j) < ((int)(P).size()); (j)++) {
        if (endsWith(t, P[j]) &&
            (id == -1 || (int)(P[j]).size() > (int)(P[id]).size())) {
          id = j;
        }
      }
      nxt[i][c - '0'] = id;
      id = -1;
      for (int(j) = 0; (j) < ((int)(s).size()); (j)++) {
        if (endsWith(t, s[j]) &&
            (id == -1 || (int)(s[j]).size() > (int)(s[id]).size())) {
          id = j;
        }
      }
      fs[i][c - '0'] = id;
    }
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    int I = i % 2;
    int J = 1 - I;
    memset(dp[J], 0, sizeof(dp[J]));
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k < M; k++) {
        if ((int)(P[k]).size() <= i) {
          for (int(c) = 0; (c) < (4); (c)++) {
            int x = fs[k][c];
            if (x != -1 && i - (int)(s[x]).size() + 1 <= j) {
              dp[J][nxt[k][c]][i + 1] += dp[I][k][j];
              dp[J][nxt[k][c]][i + 1] %= MOD;
            } else {
              dp[J][nxt[k][c]][j] += dp[I][k][j];
              dp[J][nxt[k][c]][j] %= MOD;
            }
          }
        }
      }
    }
  }
  int res = 0, I = n % 2;
  for (int(i) = 0; (i) < ((int)(P).size()); (i)++) {
    res += dp[I][i][n];
    res %= MOD;
  }
  printf("%d\n", res);
  return 0;
}
