#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
string rule[11];
string prefix[110];
int maxrule[110];
int t[110][4];
char dic[] = {'A', 'C', 'G', 'T'};
int n, m, np;
int d[1010][110][11];
void GaoDic() {
  for (int i = 0; i < np; ++i) {
    for (int j = 0; j < m; ++j) {
      if (prefix[i].length() >= rule[j].length() &&
          prefix[i].substr(prefix[i].length() - rule[j].length()) == rule[j]) {
        maxrule[i] = max(maxrule[i], (int)rule[j].length());
      }
    }
  }
}
void GaoEdge() {
  for (int i = 0; i < np; ++i) {
    for (int k = 0; k < 4; ++k) {
      string ts = prefix[i] + dic[k];
      for (int j = 0; j < np; ++j) {
        if (ts.length() >= prefix[j].length() &&
            ts.substr(ts.length() - prefix[j].length()) == prefix[j] &&
            prefix[j].length() > prefix[t[i][k]].length()) {
          t[i][k] = j;
        }
      }
    }
  }
}
void DP() {
  d[0][0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < np; ++j) {
      for (int k = 0; k <= prefix[j].length(); ++k) {
        if (!d[i][j][k]) continue;
        for (int c = 0; c < 4; ++c) {
          int nj = t[j][c];
          if (maxrule[nj] >= k + 1) {
            d[i + 1][nj][0] = (d[i + 1][nj][0] + d[i][j][k]) % MOD;
          } else if (k + 1 <= prefix[nj].length()) {
            d[i + 1][nj][k + 1] = (d[i + 1][nj][k + 1] + d[i][j][k]) % MOD;
          }
        }
      }
    }
  }
}
int main() {
  prefix[np++] = "";
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> rule[i];
    for (int j = 1; j <= rule[i].length(); ++j) {
      prefix[np++] = rule[i].substr(0, j);
    }
  }
  sort(prefix, prefix + np);
  np = unique(prefix, prefix + np) - prefix;
  GaoDic();
  GaoEdge();
  DP();
  int ans = 0;
  for (int i = 0; i < np; ++i) {
    ans = (ans + d[n][i][0]) % MOD;
  }
  cout << ans << endl;
  return 0;
}
