"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>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
const int MOD = 1000 * 1000 * 1000 + 9;
struct tver {
  int ne[4];
  bool fl;
  int pch, pr;
};
char s[110];
int n, k;
int l;
tver ver[110];
int cn;
int df[110][11][1010];
int ras[110];
int ds[110];
int dgo[110][5];
int dma[110];
int get(char c) {
  if (c == 'A') return 0;
  if (c == 'C') return 1;
  if (c == 'G') return 2;
  return 3;
}
int newv() {
  int nv = cn++;
  ver[nv].fl = 0;
  memset(ver[nv].ne, -1, sizeof(ver[nv].ne));
  return nv;
}
void add(int pos, int v) {
  if (pos == l) {
    ver[v].fl = 1;
    return;
  }
  int nn = get(s[pos]);
  if (ver[v].ne[nn] != -1) {
    add(pos + 1, ver[v].ne[nn]);
  } else {
    int nv = newv();
    ver[v].ne[nn] = nv;
    ras[nv] = pos + 1;
    ver[nv].pch = nn;
    ver[nv].pr = v;
    add(pos + 1, nv);
  }
}
int go(int u, int c);
int suf(int u) {
  if (u == 0) return 0;
  if (ver[u].pr == 0) return 0;
  return ds[u] = go(suf(ver[u].pr), ver[u].pch);
}
int go(int u, int c) {
  if (dgo[u][c] != -1) return dgo[u][c];
  if (ver[u].ne[c] != -1) return ver[u].ne[c];
  if (u == 0) return 0;
  return dgo[u][c] = go(suf(u), c);
}
int mar(int u) {
  if (u == 0) return 0;
  if (dma[u] != -1) return dma[u];
  int res = 0;
  if (ver[u].fl)
    res = ras[u];
  else
    res = mar(suf(u));
  return dma[u] = res;
}
int f(int nv, int k, int len) {
  if (mar(nv) >= k) k = 0;
  if (k >= 10) return 0;
  if (len == n) {
    if (k == 0) return 1;
    return 0;
  }
  if (df[nv][k][len] != -1) return df[nv][k][len];
  int res = 0;
  for (int i = (0); i < (4); i++) {
    int nev = go(nv, i);
    if (ras[nev] <= k) continue;
    res += f(nev, k + 1, len + 1);
    if (res >= MOD) res -= MOD;
  }
  return df[nv][k][len] = res;
}
void solve() { printf("%d\n", f(0, 0, 0)); }
int main() {
  memset(df, -1, sizeof(df));
  memset(dgo, -1, sizeof(dgo));
  memset(ds, -1, sizeof(ds));
  memset(dma, -1, sizeof(dma));
  scanf("%d%d", &n, &k);
  memset(ver[0].ne, -1, sizeof(ver[0].ne));
  cn = 1;
  for (int i = (0); i < (k); i++) {
    scanf("%s", s);
    l = strlen(s);
    add(0, 0);
  }
  solve();
  return 0;
}
