"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;
struct Tree_Node {
  int nxt[30], pre, word, fail, len;
  char ch;
} Tree[500];
const char opt[4] = {'A' - 'A', 'C' - 'A', 'G' - 'A', 'T' - 'A'};
int Index = 1, N, M, p, tot, f[500][1050][12], ans;
char s[100];
int cal(int x) {
  if (x == 1) return 0;
  int tmp = Tree[Tree[x].pre].fail;
  while (tmp && Tree[tmp].nxt[Tree[x].ch] == 0) tmp = Tree[tmp].fail;
  if (!tmp)
    return 1;
  else
    return Tree[tmp].nxt[Tree[x].ch];
}
void ins(char *s, int id) {
  int len = strlen(s), p = 1;
  for (int i = 0; i < len; ++i) {
    s[i] -= 'A';
    if (!Tree[p].nxt[s[i]])
      Tree[p].nxt[s[i]] = ++Index, Tree[Index].ch = s[i], Tree[Index].pre = p;
    p = Tree[p].nxt[s[i]];
  }
  Tree[p].word = id;
  Tree[p].len = len;
}
void build() {
  queue<int> Q;
  Q.push(1);
  while (Q.size()) {
    int u = Q.front();
    Q.pop();
    Tree[u].fail = cal(u);
    if (Tree[Tree[u].fail].len > Tree[u].len)
      Tree[u].len = Tree[Tree[u].fail].len;
    for (int i = 0; i < 26; ++i)
      if (Tree[u].nxt[i]) Q.push(Tree[u].nxt[i]);
  }
}
const int inf = 1000000009;
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; ++i) {
    scanf("%s", s);
    if (strlen(s) <= N) ins(s, i);
  }
  build();
  f[1][0][0] = 1;
  for (int j = 0; j <= N; ++j)
    for (int i = 1; i <= Index; ++i)
      for (int l = 0; l <= 10; ++l)
        if (f[i][j][l]) {
          for (int k = 0; k < 4; ++k) {
            int p = i;
            while (p != 1 && !Tree[p].nxt[opt[k]]) p = Tree[p].fail;
            p = Tree[p].nxt[opt[k]];
            int tl = l + 1;
            if (tl <= Tree[p].len) tl = 0;
            if (tl > 10) continue;
            f[p][j + 1][tl] += f[i][j][l], f[p][j + 1][tl] %= inf;
          }
        }
  for (int i = 1; i <= Index; ++i) ans += f[i][N][0], ans %= inf;
  printf("%d\n", ans);
  return 0;
}
