"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>
const int mod = 1e9 + 9;
using namespace std;
namespace Trie {
int nxt[1010][4], fail[1010];
int end[10010], tot, root, id[300];
int dp[1001][101][12], mx[1001];
int newnode() {
  for (int i = 0; i < 4; i++) nxt[tot][i] = -1;
  fail[tot] = end[tot] = mx[tot] = 0;
  return tot++;
}
void init() {
  id['A'] = 0, id['G'] = 1, id['C'] = 2;
  id['T'] = 3;
  tot = 0;
  root = newnode();
}
int idx(char now) { return id[now]; }
void insert(char s[], int tp) {
  int p = root, len = strlen(s);
  for (int i = 0; s[i]; i++) {
    if (nxt[p][idx(s[i])] == -1) nxt[p][idx(s[i])] = newnode();
    p = nxt[p][idx(s[i])];
  }
  mx[p] = max(mx[p], len);
}
void build() {
  queue<int> que;
  que.push(root);
  while (!que.empty()) {
    int p = que.front();
    que.pop();
    end[p] = end[fail[p]];
    mx[p] = max(mx[fail[p]], mx[p]);
    for (int i = 0; i < 4; i++) {
      if (~nxt[p][i]) {
        if (p == root)
          fail[nxt[p][i]] = root;
        else
          fail[nxt[p][i]] = nxt[fail[p]][i];
        que.push(nxt[p][i]);
      } else {
        if (p == root)
          nxt[p][i] = root;
        else
          nxt[p][i] = nxt[fail[p]][i];
      }
    }
  }
}
void add(int &a, int b) { a = a + b >= mod ? a + b - mod : a + b; }
int query(int n, int m) {
  dp[0][root][0] = 1;
  for (int _ = 0; _ < n; _++) {
    for (int i = 0; i < tot; i++) {
      for (int len = 0; len <= 10; len++) {
        if (!dp[_][i][len]) continue;
        for (int j = 0; j < 4; j++) {
          if (mx[nxt[i][j]] >= len + 1)
            add(dp[_ + 1][nxt[i][j]][0], dp[_][i][len]);
          else
            add(dp[_ + 1][nxt[i][j]][len + 1], dp[_][i][len]);
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < tot; i++) add(ans, dp[n][i][0]);
  return ans;
}
};  // namespace Trie
char s[20];
int main(int argc, char const *argv[]) {
  int n, m;
  scanf("%d%d", &n, &m);
  Trie::init();
  for (int i = 0; i < m; i++) scanf("%s", s), Trie::insert(s, i);
  Trie::build();
  printf("%d\n", Trie::query(n, m));
  return 0;
}
