"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;
namespace AhoCorasickAutomata {
const char *dict = "ACGT";
const int sgm = 4, ndsz = (int)1e3 + 50, mod = (int)1e9 + 9, mxln = 11;
struct Node {
  Node *ch[sgm], *fail;
  int del[sgm], id, ln;
} pool[ndsz], *ptp, *root, *que[ndsz], **hd, **tl;
long long sz, dp[ndsz][ndsz][mxln];
Node *new_node() {
  memset(ptp, 0, sizeof(*ptp));
  ptp->id = ptp - pool, ++sz;
  return ptp++;
}
void init() { sz = 0, ptp = pool, root = new_node(); }
inline int idx(char c) {
  for (int i = 0; i < (sgm); ++i)
    if (c == dict[i]) return i;
  return -1;
}
inline void add(long long &a, long long b) { (a += b) %= mod; }
void insert(char *s) {
  Node *v = root;
  int i;
  for (i = 0; s[i]; ++i) {
    if (!v->ch[idx(s[i])]) v->ch[idx(s[i])] = new_node();
    v = v->ch[idx(s[i])];
  }
  v->ln = i;
}
void get_fail() {
  hd = tl = que;
  for (int i = 0; i < (sgm); ++i) {
    if (root->ch[i])
      (*tl++ = root->ch[i])->fail = root;
    else
      root->del[i] = true, root->ch[i] = root;
  }
  while (hd != tl) {
    Node *v = *hd++;
    for (int i = 0; i < (sgm); ++i) {
      if (v->ch[i]) {
        v->ch[i]->fail = v->fail->ch[i];
        v->ch[i]->ln = max(v->ch[i]->ln, v->ch[i]->fail->ln);
        *tl++ = v->ch[i];
      } else
        v->del[i] = true, v->ch[i] = v->fail->ch[i];
    }
  }
}
long long search(int n) {
  dp[0][0][0] = 1;
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (sz); ++j)
      for (int l = 0; l < (mxln); ++l)
        for (int k = 0; k < (sgm); ++k) {
          int ni = i + 1, nj = pool[j].ch[k]->id, nl = l + 1;
          if (nl > ni || nl >= mxln) continue;
          if (pool[nj].ln >= nl) nl = 0;
          add(dp[ni][nj][nl], dp[i][j][l]);
        }
  long long ans = 0;
  for (int j = 0; j < (sz); ++j) add(ans, dp[n][j][0]);
  return ans;
}
}  // namespace AhoCorasickAutomata
int main(int argc, char *argv[]) {
  int n, m;
  char buf[20];
  scanf("%d%d", &n, &m);
  AhoCorasickAutomata::init();
  for (int i = 0; i < (m); ++i) {
    scanf("%s", buf);
    AhoCorasickAutomata::insert(buf);
  }
  AhoCorasickAutomata::get_fail();
  long long ans = AhoCorasickAutomata::search(n);
  cout << ans << endl;
  return 0;
}
