"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 = 1e9;
inline int read() {
  int X = 0, w = 0;
  char ch = 0;
  while (!isdigit(ch)) {
    w |= ch == '-';
    ch = getchar();
  }
  while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
  return w ? -X : X;
}
const long long mod = 1000000009;
int n, m;
int sz = 1, root = 1;
int dat[101][5];
int fail[101];
int a[11];
int en[101], maxx[101];
int dp[1001][101][11];
int ID(char xx) {
  if (xx == 'A') {
    return 1;
  }
  if (xx == 'T') {
    return 2;
  }
  if (xx == 'C') {
    return 3;
  }
  return 4;
}
struct AC_machine {
  void add(string s) {
    int l = s.size();
    int p = root;
    for (int i = 0; i < l; i++) {
      a[i] = ID(s[i]);
      if (!dat[p][a[i]]) {
        dat[p][a[i]] = ++sz;
      }
      p = dat[p][a[i]];
    }
    en[p] = l;
  }
  void build() {
    queue<int> q;
    q.push(root);
    fail[root] = 0;
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int i = 1; i <= 4; i++) {
        if (dat[x][i]) {
          int p = fail[x];
          while (!dat[p][i] and p) {
            p = fail[p];
          }
          if (!p) {
            p = 1;
          } else {
            p = dat[p][i];
          }
          fail[dat[x][i]] = p;
          q.push(dat[x][i]);
          maxx[dat[x][i]] = max(en[dat[x][i]], maxx[fail[dat[x][i]]]);
        }
      }
    }
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= 4; j++) {
        if (!dat[i][j]) {
          int p = fail[i];
          while (p and !dat[p][j]) {
            p = fail[p];
          }
          if (!p) {
            p = 1;
          } else {
            p = dat[p][j];
          }
          dat[i][j] = p;
        }
      }
    }
  }
} AC;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    string s;
    cin >> s;
    AC.add(s);
  }
  AC.build();
  dp[0][1][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= sz; j++) {
      for (int k = 0; k < 10; k++) {
        for (int l = 1; l <= 4; l++) {
          if (dat[j][l]) {
            if (k + 1 <= maxx[dat[j][l]]) {
              dp[i + 1][dat[j][l]][0] += dp[i][j][k];
              dp[i + 1][dat[j][l]][0] %= mod;
            } else {
              dp[i + 1][dat[j][l]][k + 1] += dp[i][j][k];
              dp[i + 1][dat[j][l]][k + 1] %= mod;
            }
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 1; i <= sz; i++) {
    res += dp[n][i][0] % mod;
    res %= mod;
  }
  cout << res << endl;
  return 0;
}
