"Multidimensional spaces are completely out of style these days, unlike genetics problems" — thought physicist Woll and changed his subject of study to bioinformatics. Analysing results of sequencing he faced the following problem concerning DNA sequences. We will further think of a DNA sequence as an arbitrary string of uppercase letters "A", "C", "G" and "T" (of course, this is a simplified interpretation).

Let w be a long DNA sequence and s1, s2, ..., sm — collection of short DNA sequences. Let us say that the collection filters w iff w can be covered with the sequences from the collection. Certainly, substrings corresponding to the different positions of the string may intersect or even cover each other. More formally: denote by |w| the length of w, let symbols of w be numbered from 1 to |w|. Then for each position i in w there exist pair of indices l, r (1 ≤ l ≤ i ≤ r ≤ |w|) such that the substring w[l ... r] equals one of the elements s1, s2, ..., sm of the collection.

Woll wants to calculate the number of DNA sequences of a given length filtered by a given collection, but he doesn't know how to deal with it. Help him! Your task is to find the number of different DNA sequences of length n filtered by the collection {si}.

Answer may appear very large, so output it modulo 1000000009.

Input

First line contains two integer numbers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10) — the length of the string and the number of sequences in the collection correspondently. 

Next m lines contain the collection sequences si, one per line. Each si is a nonempty string of length not greater than 10. All the strings consist of uppercase letters "A", "C", "G", "T". The collection may contain identical strings.

Output

Output should contain a single integer — the number of strings filtered by the collection modulo 1000000009 (109 + 9).

Examples

Input

2 1
A


Output

1


Input

6 2
CAT
TACT


Output

2

Note

In the first sample, a string has to be filtered by "A". Clearly, there is only one such string: "AA".

In the second sample, there exist exactly two different strings satisfying the condition (see the pictures below).

<image> <image>
#include <bits/stdc++.h>
using namespace std;
template <typename T>
int size(T &a) {
  return (int)a.size();
}
template <typename T>
T sqr(T a) {
  return a * a;
}
const int INF = (int)1e9;
const long long mod = INF + 9;
struct node {
  int nxt[4];
  int link;
  int parent;
  char pchar;
  bool leaf;
  void init() {
    memset((nxt), (255), sizeof(nxt));
    link = -1;
    parent = -1;
    pchar = -1;
    leaf = false;
  }
};
int get(char x) {
  if (x == 'A') return 0;
  if (x == 'C') return 1;
  if (x == 'G') return 2;
  if (x == 'T') return 3;
  assert(false);
}
char getI(int x) {
  if (x == 0) return 'A';
  if (x == 1) return 'C';
  if (x == 2) return 'G';
  if (x == 3) return 'T';
  assert(false);
}
node trie[110];
int sz;
void init_trie() {
  trie[0].init();
  sz = 1;
  trie[0].link = 0;
}
void addString(char *s) {
  int v = 0;
  for (int i = (0); i < (strlen(s)); ++i) {
    if (trie[v].nxt[get(s[i])] != -1)
      v = trie[v].nxt[get(s[i])];
    else {
      trie[v].nxt[get(s[i])] = sz;
      trie[sz].init();
      trie[sz].parent = v;
      trie[sz].pchar = get(s[i]);
      v = sz;
      ++sz;
    }
  }
  trie[sz].leaf = true;
}
int go(int v, int c);
int getLink(int v) {
  int &g = trie[v].link;
  if (g == -1) {
    if (v == 0 || trie[v].parent == 0)
      g = 0;
    else {
      g = go(getLink(trie[v].parent), trie[v].pchar);
    }
  }
  return g;
}
int go(int v, int c) {
  int &g = trie[v].nxt[c];
  if (g == -1) {
    if (v == 0)
      g = 0;
    else
      g = go(getLink(v), c);
  }
  return g;
}
int n, m;
char s[12][12];
int maxLen[110];
char st[110];
bool check(char *s, int from, int to, char *other, int fromOther, int toOther) {
  if (toOther - fromOther != to - from) return false;
  for (int i = from, j = fromOther; i <= to; ++i, ++j)
    if (s[i] != other[j]) return false;
  return true;
}
void dfs(int v, int ptr) {
  maxLen[v] = 0;
  for (int i = (0); i < (ptr); ++i) {
    for (int j = (0); j < (m); ++j) {
      if (check(st, i, ptr - 1, s[j], 0, strlen(s[j]) - 1))
        maxLen[v] = max(maxLen[v], (int)strlen(s[j]));
    }
  }
  for (int i = (0); i < (4); ++i) {
    if (trie[v].nxt[i] != -1) {
      st[ptr] = getI(i);
      dfs(trie[v].nxt[i], ptr + 1);
    }
  }
}
int dm[2][1010][110];
void build() {
  init_trie();
  scanf("%d%d\n", &n, &m);
  for (int i = (0); i < (m); ++i) {
    gets(s[i]);
    addString(s[i]);
  }
  dfs(0, 0);
  memset((dm), (0), sizeof(dm));
  dm[0][0][0] = 1;
  for (int i = (1); i < (n + 1); ++i) {
    memset((dm[i & 1]), (0), sizeof(dm[i & 1]));
    for (int j = (max(0, i - 20)); j < (i); ++j)
      for (int vertex = (0); vertex < (sz); ++vertex)
        for (int ch = (0); ch < (4); ++ch) {
          int &tmp = dm[(i & 1) ^ 1][j][vertex];
          if (tmp == 0) continue;
          int nvertex = go(vertex, ch);
          int mlen = maxLen[nvertex];
          int nj = (i - j <= mlen ? i : j);
          dm[i & 1][nj][nvertex] += tmp;
          if (dm[i & 1][nj][nvertex] >= mod) dm[i & 1][nj][nvertex] -= mod;
        }
  }
  int res = 0;
  for (int i = (0); i < (sz); ++i) {
    res = (res + dm[n & 1][n][i]) % mod;
  }
  cout << res;
}
int main() { build(); }
