"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 double pi = acos(-1.0);
long long l, r;
long long g(long long x) {
  long long t = 1;
  while (t <= x) t *= 10;
  return (t - 1 - x) * x;
}
int n, m;
const char let[] = "ACGT";
char buf[1600];
int len[16];
int a[16][16];
vector<int> st;
struct Node {
  Node* ch[4];
  Node* next[4];
  int end;
  Node() {
    memset(a, 0, sizeof a);
    ;
  }
  void mark(Node* root) {
    end = 0;
    for (int i = 0, _n = (m); i < _n; i++)
      if (len[i] <= (int)(st).size()) {
        bool eq = true;
        for (int k = 0, _n = (len[i]); k < _n; k++)
          if (st[(int)(st).size() - len[i] + k] != a[i][k]) {
            eq = false;
            break;
          }
        if (eq) {
          end = max(end, len[i]);
        }
      }
    for (int i = 0, _n = (4); i < _n; i++)
      if (ch[i]) {
        st.push_back(i);
        ch[i]->mark(root);
        st.pop_back();
        next[i] = ch[i];
      } else {
        st.push_back(i);
        next[i] = 0;
        for (int j = 0, _n = ((int)(st).size() + 1); j < _n; j++)
          if (j > 0) {
            Node* v = root;
            for (int jj = j; jj < (int)(st).size() && v; jj++)
              v = v->ch[st[jj]];
            if (v) {
              next[i] = v;
              break;
            }
          }
        st.pop_back();
      }
  }
};
Node nodes[1024];
int w;
int d[1024][128][11];
int main() {
  gets(buf);
  sscanf(buf, "%d%d", &n, &m);
  for (int i = 0, _n = (m); i < _n; i++) {
    gets(buf);
    len[i] = strlen(buf);
    for (int j = 0, _n = (len[i]); j < _n; j++)
      a[i][j] = strchr(let, buf[j]) - let;
  }
  w = 1;
  for (int i = 0, _n = (m); i < _n; i++) {
    Node* v = &nodes[0];
    for (int j = 0, _n = (len[i]); j < _n; j++) {
      if (v->ch[a[i][j]] == 0) v->ch[a[i][j]] = &nodes[w++];
      v = v->ch[a[i][j]];
    }
  }
  nodes[0].mark(&nodes[0]);
  memset(d, 0, sizeof d);
  ;
  d[0][0][0] = 1;
  for (int i = 0, _n = (n); i < _n; i++)
    for (int j = 0, _n = (w); j < _n; j++)
      for (int c = 0, _n = (11); c < _n; c++)
        if (d[i][j][c])
          for (int add = 0, _n = (4); add < _n; add++) {
            int nc = c + 1;
            Node* v = nodes[j].next[add];
            if (v->end >= nc) nc = 0;
            if (nc == 10) continue;
            d[i + 1][v - nodes][nc] =
                (d[i + 1][v - nodes][nc] + d[i][j][c]) % 1000000009;
          }
  long long res = 0;
  for (int j = 0, _n = (w); j < _n; j++) res = (res + d[n][j][0]) % 1000000009;
  cout << res << endl;
  return 0;
}
