"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 INF = 2e9;
const double eps = 1e-12;
template <typename T>
inline void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
const long long ALL = 110, LEN = 1010, U = 4, N = 12;
const long long P = 1000000009;
long long Len, n;
namespace AC {
long long ch[ALL][U], fail[ALL], ref[ALL], lst[ALL], dep[ALL], las = 0, rt = 0,
                                                               ind = 0;
inline void Insert(long long x) {
  if (!ch[las][x]) {
    ch[las][x] = ++ind;
    dep[ind] = dep[las] + 1;
  }
  las = ch[las][x];
}
long long que[N * N], h = 1, t = 0;
inline void Build() {
  h = 1;
  t = 0;
  for (long long i = 0; i < U; i++)
    if (ch[rt][i]) {
      long long v = ch[rt][i];
      que[++t] = v;
      fail[v] = rt;
    }
  while (h <= t) {
    long long u = que[h++];
    for (long long i = 0; i < U; i++) {
      long long &v = ch[u][i], w = ch[fail[u]][i];
      if (v)
        fail[v] = w, que[++t] = v;
      else
        v = w;
      lst[v] = ref[fail[v]] ? fail[v] : lst[fail[v]];
    }
  }
}
}  // namespace AC
char s[12][20];
long long len[12];
struct NODE {
  long long u, st, d;
};
long long f[ALL][LEN][12];
bool inq[ALL][LEN][12];
NODE que[ALL * LEN * 10];
long long h = 1, t = 0;
long long ans = 0;
inline long long trans(char ch) {
  if (ch == 'A') return 0;
  if (ch == 'C') return 1;
  if (ch == 'G') return 2;
  if (ch == 'T') return 3;
  throw;
}
signed main() {
  read(Len);
  read(n);
  for (long long i = 1; i <= n; i++) {
    scanf("%s", s[i] + 1);
    len[i] = strlen(s[i] + 1);
    AC::las = AC::rt;
    for (long long j = 1; j <= len[i]; j++) AC::Insert(trans(s[i][j]));
    AC::ref[AC::las] = i;
  }
  AC::Build();
  f[AC::rt][0][0] = 1;
  que[++t] = (NODE){AC::rt, 0};
  inq[AC::rt][0][0] = 1;
  while (h <= t) {
    NODE tmp = que[h++];
    long long u = tmp.u, st = tmp.st, d = tmp.d;
    long long val = f[u][st][d];
    if (st == Len) {
      if (!d) (ans += f[u][st][d]) %= P;
      continue;
    }
    long long tst = st + 1;
    for (long long i = 0; i < U; i++) {
      long long v = AC::ch[u][i], td = d + 1;
      if (AC::dep[v] < td) continue;
      if (AC::ref[v])
        td = 0;
      else if (AC::dep[AC::lst[v]] >= td)
        td = 0;
      (f[v][tst][td] += val) %= P;
      if (!inq[v][tst][td]) que[++t] = (NODE){v, tst, td}, inq[v][tst][td] = 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
