"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 node {
  string prefix;
  int dep;
  int next[4];
  node(void) {
    dep = 0;
    for (int i = 0; i < 4; i++) next[i] = -1;
  }
};
node V[2000];
string S[10];
set<string> PRE;
map<pair<int, string>, int> M;
int main(int argc, char *argv[]) {
  int i, j, k, n, m, t;
  cin >> m >> n;
  for (i = 0; i < n; i++) {
    cin >> S[i];
    for (j = 0; S[i][j]; j++) {
      if (S[i][j] == 'C')
        S[i][j] = 'B';
      else if (S[i][j] == 'G')
        S[i][j] = 'C';
      else if (S[i][j] == 'T')
        S[i][j] = 'D';
    }
  }
  PRE.insert("");
  for (i = 0; i < n; i++)
    for (j = 1; j <= S[i].size(); j++) {
      PRE.insert(S[i].substr(0, j));
    }
  int head = 0, tail = 1;
  M[pair<int, string>(0, "")] = 0;
  while (head < tail) {
    for (char c = 'A'; c <= 'D'; c++) {
      string str = V[head].prefix + c;
      for (t = 0; t < str.size(); t++)
        if (PRE.find(str.substr(t, str.size() - t)) != PRE.end()) break;
      if (t <= V[head].dep) {
        string sub = str.substr(t, str.size() - t);
        for (k = 0; k < n; k++) {
          if (S[k].size() <= sub.size() &&
              S[k].size() + V[head].dep - t >= sub.size() &&
              S[k] == sub.substr(sub.size() - S[k].size(), S[k].size()))
            break;
        }
        if (k < n) {
          if (M.find(pair<int, string>(sub.size(), sub)) != M.end())
            V[head].next[c - 'A'] = M[pair<int, string>(sub.size(), sub)];
          else {
            V[tail].prefix = sub;
            V[tail].dep = sub.size();
            V[head].next[c - 'A'] = tail;
            M.insert(pair<pair<int, string>, int>(
                pair<int, string>(sub.size(), sub), tail));
            tail++;
          }
        } else {
          if (M.find(pair<int, string>(V[head].dep - t, sub)) != M.end())
            V[head].next[c - 'A'] = M[pair<int, string>(V[head].dep - t, sub)];
          else {
            V[tail].prefix = sub;
            V[tail].dep = V[head].dep - t;
            V[head].next[c - 'A'] = tail;
            M.insert(pair<pair<int, string>, int>(
                pair<int, string>(V[head].dep - t, sub), tail));
            tail++;
          }
        }
      }
    }
    head++;
  }
  int *pre = new int[head];
  int *next = new int[head];
  for (i = 1; i < head; i++) pre[i] = 0;
  pre[0] = 1;
  for (k = 0; k < m; k++) {
    for (i = 0; i < head; i++) next[i] = 0;
    for (i = 0; i < head; i++)
      for (j = 0; j < 4; j++)
        if (V[i].next[j] >= 0)
          next[V[i].next[j]] = (next[V[i].next[j]] + pre[i]) % 1000000009;
    int *tmp = pre;
    pre = next;
    next = tmp;
  }
  int res = 0;
  for (i = 0; i < head; i++)
    if (V[i].dep == V[i].prefix.size()) res = (res + pre[i]) % 1000000009;
  delete[] pre;
  delete[] next;
  cout << res;
  return 0;
}
