"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;
const int N = 205, oo = 1000000009;
int c[N][6], d[N], e[N], q[N], f[N][12], g[N][12], n, m, Q, ans;
char s[N];
void update(int &x, int y) {
  x += y;
  if (x >= oo) x -= oo;
}
void pre() {
  n = 1, *c[1] = 0;
  for (int i = 1; i <= 4; i++) c[0][i] = 1;
}
int change(char ch) {
  return ch == 'A' ? 1 : ch == 'C' ? 2 : ch == 'G' ? 3 : 4;
}
void ins() {
  scanf("%s", s + 1);
  int L = strlen(s + 1), x = 1, y;
  for (int i = 1; i <= L; i++) {
    y = change(s[i]);
    if (!c[x][y]) c[x][y] = ++n;
    x = c[x][y];
  }
  d[x] = L;
}
void bfs() {
  int h = 0, t = 1;
  q[1] = 1;
  while (h < t) {
    int x = q[++h], y;
    for (int i = 1; i <= 4; i++)
      if (y = c[x][i]) {
        int fail = *c[x];
        while (fail && !c[fail][i]) fail = *c[fail];
        *c[y] = c[fail][i], q[++t] = y;
        if (d[*c[y]] && !d[y]) d[y] = d[*c[y]];
      } else
        c[x][i] = c[*c[x]][i];
  }
}
int main() {
  scanf("%d%d", &Q, &m);
  pre();
  for (int i = 1; i <= m; i++) ins();
  bfs();
  f[1][0] = 1;
  while (Q--) {
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++)
      for (int k = 1; k <= 4; k++)
        for (int j = 1; j <= 10; j++) update(g[c[i][k]][j], f[i][j - 1]);
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
      if (d[i]) {
        for (int j = 1; j <= 10; j++)
          if (j <= d[i])
            update(*f[i], g[i][j]);
          else
            update(f[i][j], g[i][j]);
      } else
        memcpy(f[i], g[i], sizeof(f[i]));
  }
  for (int i = 1; i <= n; i++)
    if (d[i]) update(ans, *f[i]);
  printf("%d\n", ans);
  return 0;
}
