"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>
int dr[] = {2, 2, -2, -2, 1, -1, 1, -1};
int dc[] = {1, -1, 1, -1, 2, 2, -2, -2};
int dr1[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dc1[] = {1, -1, 1, 0, -1, 0, 1, -1};
int dr2[] = {0, 0, 1, -1};
int dc2[] = {1, -1, 0, 0};
using namespace std;
long long int f[505];
struct state {
  int to[26];
  int depth;
  int suffLink;
  int par;
  int parLet;
  int cnt;
  int nxt[26];
};
vector<int> g[2004 + 500];
state states[2004 + 500];
int totNodes;
inline int add(string &str, long long int x) {
  int cur = 1;
  int len = str.size();
  for (int i = 0; i < len; i++) {
    char c = str[i];
    if (!states[cur].to[c - 'a']) {
      states[cur].to[c - 'a'] = ++totNodes;
      states[totNodes].par = cur;
      states[totNodes].depth = states[cur].depth + 1;
      states[totNodes].parLet = c - 'a';
    }
    cur = states[cur].to[c - 'a'];
  }
  states[cur].cnt++;
  f[cur] = max(f[cur], x);
  return cur;
}
void pushLinks() {
  queue<int> Q;
  Q.push(1);
  while (!Q.empty()) {
    int node = Q.front();
    Q.pop();
    if (states[node].depth <= 1) {
      states[node].suffLink = 1;
    } else {
      int cur = states[states[node].par].suffLink;
      int parLet = states[node].parLet;
      while (cur > 1 and !states[cur].to[parLet]) {
        cur = states[cur].suffLink;
      }
      if (states[cur].to[parLet]) {
        cur = states[cur].to[parLet];
      }
      states[node].suffLink = cur;
    }
    if (node != 1) g[states[node].suffLink].push_back(node);
    for (int i = 0; i < 26; i++) {
      if (states[node].to[i]) {
        Q.push(states[node].to[i]);
      }
    }
  }
}
void dfs(int u, int p) {
  if (p != -1) {
    f[u] = max(f[u], f[p]);
    states[u].cnt += states[p].cnt;
  }
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (v == p) continue;
    dfs(v, u);
  }
}
int Next(int from, char ch) {
  if (states[from].nxt[ch - 'a']) return states[from].nxt[ch - 'a'];
  int cur = from;
  int c = ch - 'a';
  while (cur > 1 and !states[cur].to[c]) {
    cur = states[cur].suffLink;
  }
  if (states[cur].to[c]) {
    cur = states[cur].to[c];
  }
  return states[from].nxt[ch - 'a'] = cur;
}
long long int dp[1002][12][102], n;
string t1 = "agct";
long long int cal(long long int x, long long int y, long long int z) {
  long long int i, j;
  if (y > 10) return 0;
  if (x > n) return (y == 0);
  long long int &r = dp[x][y][z];
  if (r != -1) return r;
  r = 0;
  for (i = 0; i < 4; i++) {
    long long int now = Next(z, t1[i]);
    if (f[now] > y) {
      long long int r1 = cal(x + 1, 0, now);
      r += r1;
      r %= 1000000009;
    } else {
      long long int r1 = cal(x + 1, y + 1, now);
      r += r1;
      r %= 1000000009;
    }
  }
  return r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int m, i, j;
  string t;
  while (cin >> n >> m) {
    totNodes = 1;
    for (i = 0; i < m; i++) {
      cin >> t;
      for (j = 0; j < t.size(); j++) t[j] = t[j] + 32;
      add(t, t.size());
    }
    pushLinks();
    dfs(1, -1);
    memset(dp, -1, sizeof(dp));
    long long int ans = cal(1, 0, 1);
    cout << ans << endl;
  }
  return 0;
}
