#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T checkmin(T &a, T b) {
  return (a < b) ? a : a = b;
}
template <class T>
inline T checkmax(T &a, T b) {
  return (a > b) ? a : a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline T Lowbit(T x) {
  return x & (-x);
}
template <class T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (a == 0) ? b : GCD(b % a, a);
}
template <class T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return (a == 0 || b == 0) ? 0 : a / GCD(a, b) * b;
}
template <class T>
T ExtGCD(T a, T b, T &x, T &y) {
  if (a < 0) {
    T c = ExtGCD(-a, b, x, y);
    x = -x;
    return c;
  }
  if (b < 0) {
    T c = ExtGCD(a, -b, x, y);
    y = -y;
    return c;
  }
  if (a == 0) {
    x = 0, y = 1;
    return b;
  } else {
    T c = ExtGCD(b % a, a, y, x);
    x -= b / a * y;
    return c;
  }
}
const char Ch[4] = {'A', 'C', 'G', 'T'};
int N, M, Ans;
int Opt[1005][15][15][15];
bool Can[15][15][15];
bool Able[15][15][4];
pair<int, int> To[15][15][4];
string St[15];
void Add(int &a, int b) {
  a += b;
  while (a >= 1000000009) a -= 1000000009;
}
int main() {
  cin >> N >> M;
  for (int i = 1; i <= M; ++i) cin >> St[i];
  for (int i = 1; i <= M; ++i)
    for (int t = 0; t <= (int)St[i].length(); ++t)
      for (int d = 0; d < 4; ++d) {
        int best = -1;
        for (int j = 1; j <= M; ++j)
          for (int l = 0; l <= (int)min(t, (int)St[j].length() - 1); ++l) {
            bool Flag = 1;
            for (int k = 0; k < l; ++k) Flag &= (St[i][t - l + k] == St[j][k]);
            if (Flag && St[j][l] == Ch[d] && l > best)
              best = l, To[i][t][d] = make_pair(j, l + 1);
          }
        Able[i][t][d] = (best >= 0);
      }
  for (int i = 1; i <= M; ++i)
    for (int t = 0; t <= (int)St[i].length(); ++t)
      for (int g = 0; g <= t; ++g) {
        bool Flag = 0;
        for (int j = 1; j <= M; ++j)
          if ((int)St[j].length() >= g && t >= (int)St[j].length()) {
            Flag = 1;
            for (int k = 1; k <= (int)St[j].length(); ++k)
              Flag &= (St[j][St[j].length() - k] == St[i][t - k]);
            if (Flag) break;
          }
        Can[i][t][g] = Flag;
      }
  Opt[0][1][0][0] = 1;
  for (int i = 0; i <= N; ++i)
    for (int j = 1; j <= M; ++j)
      for (int k = 0; k <= (int)St[j].length(); ++k)
        for (int g = 0; g <= k; ++g)
          for (int d = 0; d < 4; ++d)
            if (Able[j][k][d] && To[j][k][d].second >= g + 1) {
              if (Can[To[j][k][d].first][To[j][k][d].second][g + 1])
                Add(Opt[i + 1][To[j][k][d].first][To[j][k][d].second][0],
                    Opt[i][j][k][g]);
              else
                Add(Opt[i + 1][To[j][k][d].first][To[j][k][d].second][g + 1],
                    Opt[i][j][k][g]);
            }
  Ans = 0;
  for (int j = 1; j <= M; ++j)
    for (int k = 0; k <= (int)St[j].length(); ++k) Add(Ans, Opt[N][j][k][0]);
  printf("%d\n", Ans);
  return 0;
}
