"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 = 105;
const int mod = 1000000009;
int tree[N][5], top;
int q[N], f[N], t[N][1005][15];
void insert(char *s, int t) {
  int rt, nxt, x;
  for (rt = 0; *s; rt = nxt, ++s) {
    if (*s == 'A')
      x = 1;
    else if (*s == 'T')
      x = 2;
    else if (*s == 'C')
      x = 3;
    else
      x = 4;
    nxt = tree[rt][x];
    if (nxt == 0) {
      top++;
      tree[rt][x] = nxt = top;
      memset(tree[top], 0, sizeof(tree[top]));
    }
  }
  tree[rt][0] = t;
}
void build() {
  int l = 1, r = 0, i, j, k, x;
  f[0] = -1;
  for (i = 1; i <= 4; i++)
    if (tree[0][i]) {
      q[++r] = tree[0][i];
      f[tree[0][i]] = 0;
    }
  while (l <= r) {
    i = q[l];
    tree[i][0] = max(tree[i][0], tree[f[i]][0]);
    for (j = 1; j <= 4; j++)
      if (tree[i][j]) {
        q[++r] = tree[i][j];
        k = f[i];
        while (k > 0 && !tree[k][j]) k = f[k];
        f[tree[i][j]] = tree[k][j];
      } else
        tree[i][j] = tree[f[i]][j];
    l++;
  }
}
int dp(int n) {
  int i, j, k, l, x, res;
  t[0][0][0] = 1;
  for (j = 0; j < n; j++)
    for (i = 0; i <= top; i++)
      for (l = 0; l <= 10; l++)
        if (t[i][j][l])
          for (k = 1; k <= 4; k++) {
            x = tree[i][k];
            if (tree[x][0] > l)
              t[x][j + 1][0] = (t[x][j + 1][0] + t[i][j][l]) % mod;
            else if (l + 1 <= 10)
              t[x][j + 1][l + 1] = (t[x][j + 1][l + 1] + t[i][j][l]) % mod;
          }
  res = 0;
  for (i = 0; i <= top; i++) res = (res + t[i][n][0]) % mod;
  return res;
}
int main() {
  char s[20];
  int n, m, i;
  scanf("%d%d", &n, &m);
  top = 0;
  memset(tree[0], 0, sizeof(tree[0]));
  for (i = 1; i <= m; i++) {
    scanf("%s", s);
    insert(s, strlen(s));
  }
  build();
  printf("%d\n", dp(n));
}
