"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 mod = 1000000009;
class Node;
int _nid;
Node *_nd[200];
class Node {
 public:
  Node *fail;
  map<char, Node *> _next;
  int d, id;
  bool marked;
  Node(int di) : d(di) {
    _nd[_nid] = this;
    id = _nid++;
    fail = NULL;
    marked = 0;
  }
  ~Node() {
    for (map<char, Node *>::iterator it = _next.begin(); it != _next.end();
         it++)
      delete it->second;
  }
  Node *build(char ch) {
    if (_next.find(ch) == _next.end()) _next[ch] = new Node(d + 1);
    return _next[ch];
  }
  Node *next(char ch) {
    if (_next.find(ch) == _next.end())
      return NULL;
    else
      return _next[ch];
  }
  Node *walk(char ch) {
    Node *v = this;
    while (v->fail != v && v->next(ch) == NULL) v = v->fail;
    if (v->next(ch) != NULL) v = v->next(ch);
    return v;
  }
};
int pn;
char p[14][14];
Node *pre[14];
int ql, qr;
Node *que[14 * 14];
inline Node *construct(Node *v, char *p) {
  while (*p) {
    v = v->build(*p);
    p++;
  }
  return v;
}
inline void construct_all(Node *ac) {
  int i;
  for (i = 0; i < pn; i++) {
    pre[i] = construct(ac, p[i]);
    pre[i]->marked = 1;
  }
}
inline void find_fail(Node *ac) {
  Node *v, *u, *f;
  char ch;
  map<char, Node *>::iterator it;
  ql = qr = 0;
  ac->fail = ac;
  for (it = ac->_next.begin(); it != ac->_next.end(); it++) {
    que[qr] = it->second;
    que[qr]->fail = ac;
    qr++;
  }
  while (ql < qr) {
    v = que[ql++];
    for (it = v->_next.begin(); it != v->_next.end(); it++) {
      ch = it->first;
      u = it->second;
      que[qr++] = u;
      f = v->fail;
      while (f != ac && f->next(ch) == NULL) f = f->fail;
      if (f->next(ch))
        u->fail = f->next(ch);
      else
        u->fail = ac;
    }
  }
}
int len;
int dp[2][1050][200];
char dna[4] = {'A', 'T', 'C', 'G'};
inline int max(int a, int b) { return a > b ? a : b; }
inline int add(int a, int b) {
  int s = a + b;
  if (s >= mod) s -= mod;
  return s;
}
inline int solve() {
  int di, i, j, vi, ui, t, sol = 0;
  Node *v, *u, *r;
  _nid = 0;
  Node ac(0);
  construct_all(&ac);
  find_fail(&ac);
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;
  for (i = 0; i < len; i++) {
    for (j = max(0, i - 14); j <= i; j++) {
      for (vi = 0; vi < _nid; vi++) {
        if (!dp[i & 1][j][vi]) continue;
        v = _nd[vi];
        for (t = 0; t < 4; t++) {
          u = v->walk(dna[t]);
          ui = u->id;
          r = u;
          while (r != &ac && !(r->marked)) r = r->fail;
          if (r->marked && i - r->d < j) {
            dp[i + 1 & 1][i + 1][ui] =
                add(dp[i & 1][j][vi], dp[i + 1 & 1][i + 1][ui]);
          } else {
            dp[i + 1 & 1][j][ui] = add(dp[i & 1][j][vi], dp[i + 1 & 1][j][ui]);
          }
        }
      }
    }
    for (j = max(0, i - 14); j <= i + 2; j++)
      for (vi = 0; vi < _nid; vi++) dp[i & 1][j][vi] = 0;
  }
  for (vi = 0; vi < _nid; vi++) sol = add(sol, dp[len & 1][len][vi]);
  return sol;
}
int main(void) {
  int i;
  scanf("%d %d", &len, &pn);
  for (i = 0; i < pn; i++) scanf("%s", p[i]);
  printf("%d\n", solve());
}
