"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;
inline int read() {
  int s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
const int inf = 2e9 + 7;
double eps = 1e-6;
const int mod = 1e9 + 9;
const int N = 1e3 + 10;
const double pi = acos(-1.0);
long long power(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long exgcd(long long a, long long b, long long& x, long long& y) {
  long long c;
  return !b ? (x = 1, y = 0, a)
            : (c = exgcd(b, a % b, y, x), y -= (a / b) * x, c);
}
long long INV(long long a) {
  long long x, y;
  exgcd(a, mod, x, y);
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
int n;
long long dp[N][N][11];
struct AC {
  int tr[N][26], tot;
  int fail[N];
  int tr2[N][26];
  int Len[N];
  bool key[N];
  int insert(char s[]) {
    int u = 0;
    for (int i = 1; s[i]; i++) {
      int c = s[i] - 'a';
      if (!tr[u][c]) tr[u][c] = ++tot;
      Len[tr[u][c]] = Len[u] + 1;
      u = tr[u][c];
    }
    key[u] = 1;
    return u;
  }
  void build() {
    for (int i = 0; i <= tot; ++i)
      for (int j = 0; j <= 3; ++j) tr2[i][j] = tr[i][j];
    queue<int> q;
    for (int i = 0; i <= 25; ++i)
      if (tr[0][i]) q.push(tr[0][i]);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int i = 0; i <= 25; ++i) {
        if (tr[u][i]) {
          fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
        } else
          tr[u][i] = tr[fail[u]][i];
      }
    }
  }
  int dfs(int u, int len, int k) {
    bool ok = key[u];
    int now = u;
    while (1) {
      now = fail[now];
      if (Len[now] >= k && key[now]) {
        ok |= 1;
        break;
      }
      if (now == 0) break;
    }
    if (ok) k = 0;
    if (!u) return 0;
    if (dp[u][len][k] != -1) return dp[u][len][k];
    if (len == n) {
      bool ok = key[u];
      int now = u;
      while (1) {
        now = fail[now];
        if (Len[now] >= k && key[now]) {
          ok |= 1;
          break;
        }
        if (now == 0) break;
      }
      return dp[u][len][k] = ok;
    }
    long long& res = dp[u][len][k] = 0;
    for (int i = 0; i <= 3; i++) {
      if (tr2[u][i])
        res += dfs(tr2[u][i], len + 1, k + 1);
      else {
        int now = u;
        while (1) {
          now = fail[now];
          if (Len[now] >= k && tr2[now][i]) {
            res += dfs(tr2[now][i], len + 1, k + 1);
            break;
          }
          if (now == 0) break;
        }
      }
    }
    res %= mod;
    return res;
  }
  int work() {
    memset(dp, -1, sizeof(dp));
    long long res = 0;
    for (int i = 0; i <= 3; i++) res += dfs(tr[0][i], 1, 1);
    res %= mod;
    return res;
  }
} ac;
char s[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int m;
  cin >> n >> m;
  map<char, char> mp;
  mp['A'] = 'a';
  mp['C'] = 'b';
  mp['T'] = 'c';
  mp['G'] = 'd';
  for (int i = 1; i <= m; ++i) {
    cin >> s + 1;
    for (int i = 1; i <= strlen(s + 1); ++i) s[i] = mp[s[i]];
    ac.insert(s);
  }
  ac.build();
  cout << ac.work() << '\n';
}
