#include <bits/stdc++.h>
using namespace std;
struct Node {
  Node *next[4], *fail;
  int val, idx;
  void init(int _idx) {
    memset(next, 0, sizeof(next));
    fail = 0;
    val = 0, idx = _idx;
  }
};
Node *root, nodes[105], *pstart, *que[105];
int np;
int dic[128], dcnt;
int getIdx(char ch) {
  if (dic[ch] == -1) dic[ch] = dcnt++;
  return dic[ch];
}
void insert(char str[], int val) {
  int i = 0, index;
  Node *cur = root;
  while (str[i]) {
    index = getIdx(str[i]);
    if (!cur->next[index]) {
      pstart->init(np++);
      cur->next[index] = pstart++;
    }
    cur = cur->next[index];
    i++;
  }
  cur->val = val;
}
void init_ac_automation() {
  np = dcnt = 0;
  memset(dic, -1, sizeof(dic));
  pstart = nodes;
  pstart->init(np++);
  root = pstart++;
}
void build_ac_automation() {
  Node *cur, *p;
  int i, head = 0, tail = 0;
  que[tail++] = root;
  while (head < tail) {
    cur = que[head++];
    for (i = 0; i < 4; i++) {
      p = cur->fail ? cur->fail->next[i] : root;
      if (cur->next[i]) {
        cur->next[i]->fail = p;
        cur->next[i]->val = max(cur->next[i]->val, p->val);
        que[tail++] = cur->next[i];
      } else
        cur->next[i] = p;
    }
  }
}
char str[15][15];
int n, m;
long long dp[1005][105][15];
int solve() {
  int i, j, k, p;
  Node *cur;
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < np; j++) {
      for (k = 0; k < 11; k++) {
        if (dp[i][j][k]) {
          dp[i][j][k] %= 1000000009;
          for (p = 0; p < 4; p++) {
            cur = nodes[j].next[p];
            if (cur->val > k)
              dp[i + 1][cur->idx][0] += dp[i][j][k];
            else if (k + 1 < 11)
              dp[i + 1][cur->idx][k + 1] += dp[i][j][k];
          }
        }
      }
    }
  }
  long long ret = 0;
  for (i = 0; i < np; i++) ret += dp[n][i][0] % 1000000009;
  return ret % 1000000009;
}
int main() {
  int t, i;
  while (scanf("%d%d", &n, &m) != EOF) {
    init_ac_automation();
    for (i = 0; i < m; i++) {
      scanf("%s", str[i]);
      insert(str[i], strlen(str[i]));
    }
    build_ac_automation();
    int ans = solve();
    printf("%d\n", ans);
  }
  return 0;
}
