"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 K = 4;
const int MOD = 1000000009;
const int S = 10;
const int N = 1000;
struct node {
  int next[K];
  int suflink;
  int h;
  int par, ch;
  node(int par, int ch, int h);
  int Next(int d);
  int Suflink();
  int maxdeg;
  int Maxdeg();
};
vector<node> nodes;
node::node(int par, int ch, int h) {
  memset(next, -1, sizeof(next));
  suflink = -1;
  maxdeg = -1;
  this->par = par;
  this->ch = ch;
  this->h = h;
}
int node::Next(int d) {
  if (next[d] == -1) next[d] = nodes[Suflink()].Next(d);
  return next[d];
}
int node::Suflink() {
  if (suflink == -1) {
    if (h == 1)
      suflink = 0;
    else
      suflink = nodes[nodes[par].Suflink()].Next(ch);
  }
  return suflink;
}
int node::Maxdeg() {
  if (maxdeg == -1) maxdeg = nodes[Suflink()].Maxdeg();
  return maxdeg;
}
int n, m;
char s[S + 1];
vector<vector<vector<int> > > fm;
int f(int v, int k, int n) {
  if (nodes[v].h < k) return 0;
  if (nodes[v].Maxdeg() >= k) k = 0;
  if (n == 0) return (k == 0) ? 1 : 0;
  if (fm[v][k][n] == -1) {
    int res = 0;
    for (int i = 0; i < K; i++)
      res = (res + f(nodes[v].Next(i), k + 1, n - 1)) % MOD;
    fm[v][k][n] = res;
  }
  return fm[v][k][n];
}
int main() {
  nodes.push_back(node(0, 0, 0));
  nodes[0].suflink = 0;
  nodes[0].maxdeg = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%s", s);
    int t = 0;
    for (int j = 0; s[j]; j++) {
      int d;
      if (s[j] == 'A')
        d = 0;
      else if (s[j] == 'C')
        d = 1;
      else if (s[j] == 'G')
        d = 2;
      else
        d = 3;
      if (nodes[t].next[d] == -1) {
        nodes[t].next[d] = nodes.size();
        nodes.push_back(node(t, d, nodes[t].h + 1));
      }
      t = nodes[t].next[d];
    }
    nodes[t].maxdeg = nodes[t].h;
  }
  for (int i = 0; i < K; i++)
    if (nodes[0].next[i] == -1) nodes[0].next[i] = 0;
  fm.resize(nodes.size(), vector<vector<int> >(S + 1, vector<int>(N + 1, -1)));
  printf("%d", f(0, 0, n));
  return 0;
}
