"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;
template <typename T>
T rd() {
  T nmb = 0;
  int sgn = 0;
  char chr = getchar();
  while (!isdigit(chr)) {
    if (chr == '-') sgn = 1;
    chr = getchar();
  }
  while (isdigit(chr)) {
    nmb = (nmb << 3) + (nmb << 1) + chr - '0';
    chr = getchar();
  }
  return sgn ? -nmb : nmb;
}
template <typename T>
void wt(T nmb) {
  if (nmb > 9) wt(nmb / 10);
  putchar(nmb % 10 + '0');
}
template <typename T>
void cmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void cmin(T &x, T y) {
  x = x < y ? x : y;
}
void proc_status() {
  freopen("/proc/self/status", "r", stdin);
  string chr;
  while (getline(cin, chr))
    if (chr[2] == 'P') {
      cerr << chr << endl;
      break;
    }
}
const int N = 1e3 + 10, M = 110, K = 10, L = 20;
const int P = 1e9 + 9;
int n, m;
char chx[M];
int ch[M][K], f[M], cnt;
int b[M];
void getACAM() {
  queue<int> que;
  for (int i = 1; i <= 4; ++i)
    if (ch[0][i]) que.push(ch[0][i]);
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    for (int i = 1; i <= 4; ++i) {
      int t = ch[f[x]][i];
      if (ch[x][i]) {
        f[ch[x][i]] = t;
        cmax(b[ch[x][i]], b[t]);
        que.push(ch[x][i]);
      } else
        ch[x][i] = t;
    }
  }
}
int Mx;
void Init() {
  n = rd<int>(), m = rd<int>();
  while (m--) {
    scanf("%s", chx + 1);
    int len = strlen(chx + 1);
    cmax(Mx, len);
    int p = 0;
    for (int i = 1; i <= len; ++i) {
      int c;
      if (chx[i] == 'A') c = 1;
      if (chx[i] == 'C') c = 2;
      if (chx[i] == 'G') c = 3;
      if (chx[i] == 'T') c = 4;
      if (!ch[p][c]) ch[p][c] = ++cnt;
      p = ch[p][c];
    }
    b[p] = len;
  }
  getACAM();
}
struct node {
  int x, st, lft;
};
const int Lim = 2e4;
struct Queue {
  int F, T, siz;
  node que[N * L * 2];
  bool empty() { return !siz; }
  void push(node x) {
    ++T;
    if (T == Lim) T = 0;
    que[T] = x;
    ++siz;
  }
  void pop() {
    ++F;
    if (F == Lim) F = 0;
    --siz;
  }
  node front() { return que[F]; }
} que;
int dp[M][2][L];
bool vis[M][2][L];
void Solve() {
  que.F = 1, que.T = 0;
  dp[0][0][0] = 1;
  vis[0][0][0] = 1;
  que.push((node){0, 0, 0});
  int Cnt = 0;
  while (!que.empty()) {
    node t = que.front();
    int x = t.x, st = t.st, lft = t.lft;
    que.pop();
    for (int i = 1; i <= 4; ++i) {
      int k = ch[x][i];
      if (b[k] >= lft + 1) {
        (dp[k][st ^ 1][0] += dp[x][st][lft]) %= P;
        if (!vis[k][st ^ 1][0]) {
          vis[k][st ^ 1][0] = 1;
          que.push((node){k, st ^ 1, 0});
        }
      } else {
        if (lft + 1 >= Mx) continue;
        (dp[k][st ^ 1][lft + 1] += dp[x][st][lft]) %= P;
        if (!vis[k][st ^ 1][lft + 1]) {
          vis[k][st ^ 1][lft + 1] = 1;
          que.push((node){k, st ^ 1, lft + 1});
        }
      }
    }
    if (!que.empty() && (st ^ que.front().st)) {
      ++Cnt;
      if (Cnt == n) break;
      for (int i = 0; i <= cnt; ++i)
        for (int j = 0; j <= Mx; ++j) dp[i][st][j] = vis[i][st][j] = 0;
    }
  }
  int Ans = 0;
  for (int i = 1, st = n & 1; i <= cnt; ++i) (Ans += dp[i][st][0]) %= P;
  printf("%d\n", Ans);
}
int main() {
  Init();
  Solve();
  return 0;
}
