#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
inline int letterToNum(char ch) {
  if (ch == 'A')
    return 0;
  else if (ch == 'C')
    return 1;
  else if (ch == 'G')
    return 2;
  else
    return 3;
}
int a, b, c, d, i, j, n, m, k;
int sm[102][4], nx[102][4];
bool en[102];
string cs[102];
int pr[102], len[102], ms[102];
char str[12];
int dp[1001][11][102];
int main() {
  scanf("%d%d", &n, &m);
  k = 1;
  memset(sm, -1, sizeof(sm));
  for (int _n((m)-1), i(0); i <= _n; i++) {
    scanf("%s", str);
    c = (int)strlen(str);
    for (int _n((c)-1), j(0); j <= _n; j++) str[j] = letterToNum(str[j]);
    a = 0;
    for (int _n((c)-1), j(0); j <= _n; j++) {
      if (sm[a][str[j]] != -1)
        a = sm[a][str[j]];
      else {
        sm[a][str[j]] = k++;
        if (j == c - 1) en[k - 1] = 1;
        cs[k - 1] = cs[a];
        cs[k - 1] += (char)(str[j] + 'A');
        a = k - 1;
      }
      if (j == c - 1) en[a] = 1;
    }
  }
  pr[0] = 0;
  for (int _n((k - 1)), i(1); i <= _n; i++) {
    if (en[i]) ms[i] = (int)((cs[i]).size());
    if ((int)((cs[i]).size()) == 1)
      pr[i] = 0;
    else {
      for (int _n((k)-1), j(0); j <= _n; j++) {
        if (en[j] && (int)((cs[j]).size()) < (int)((cs[i]).size())) {
          a = (int)((cs[j]).size());
          if (cs[i].substr((int)((cs[i]).size()) - a, a) == cs[j]) {
            ms[i] = max(ms[i], (int)((cs[j]).size()));
          }
        }
        if ((int)((cs[j]).size()) >= (int)((cs[i]).size()) ||
            (int)((cs[j]).size()) <= (int)((cs[pr[i]]).size()))
          continue;
        a = (int)((cs[j]).size());
        if (cs[i].substr((int)((cs[i]).size()) - a, a) == cs[j]) pr[i] = j;
      }
    }
  }
  memset(nx, -1, sizeof(nx));
  for (int _n((k)-1), i(0); i <= _n; i++) {
    for (int _n((4) - 1), j(0); j <= _n; j++) {
      a = i;
      while (a > 0 && sm[a][j] == -1) a = pr[a];
      nx[i][j] = sm[a][j];
    }
  }
  for (int _n((k)-1), i(0); i <= _n; i++) len[i] = (int)((cs[i]).size());
  dp[0][0][0] = 1;
  for (int _n((n)-1), i(0); i <= _n; i++) {
    for (int _n((10) - 1), j(0); j <= _n; j++) {
      for (int _n((k)-1), z(0); z <= _n; z++) {
        if (!dp[i][j][z]) continue;
        for (int _n((4) - 1), o(0); o <= _n; o++) {
          a = nx[z][o];
          if (a == -1) continue;
          b = j + 1;
          if (ms[a] >= b) b = 0;
          if (b == 10) continue;
          if (len[a] < b) continue;
          dp[i + 1][b][a] += dp[i][j][z];
          if (dp[i + 1][b][a] >= 1000000009) dp[i + 1][b][a] -= 1000000009;
        }
      }
    }
  }
  a = 0;
  for (int _n((k)-1), i(0); i <= _n; i++) {
    a += dp[n][0][i];
    if (a >= 1000000009) a -= 1000000009;
  }
  printf("%d\n", a);
}
