"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 string CHARS = "ACGT";
const int MOD = int(1e9) + 9;
int main() {
  int n, m;
  cin >> n >> m;
  vector<string> strs;
  set<string> all, ends;
  all.insert("");
  int maxL = 0;
  for (int i = 0; i < m; ++i) {
    string s;
    cin >> s;
    maxL = max(maxL, int(s.length()));
    strs.push_back(s);
    for (int j = 1; j <= s.size(); ++j) {
      all.insert(s.substr(0, j));
    }
    ends.insert(s);
  }
  map<string, int> index;
  int cnt = 0;
  for (__typeof(all.begin()) iter = all.begin(); iter != all.end(); ++iter) {
    index[*iter] = cnt++;
  }
  vector<int> maxEnd(cnt, 0);
  for (__typeof(all.begin()) iter = all.begin(); iter != all.end(); ++iter) {
    string s = *iter;
    for (__typeof(ends.begin()) iter2 = ends.begin(); iter2 != ends.end();
         ++iter2) {
      string e = *iter2;
      if (s.length() >= e.length() && s.substr(s.length() - e.length()) == e)
        maxEnd[index[s]] = max(maxEnd[index[s]], int(e.length()));
    }
  }
  vector<vector<int> > next(cnt, vector<int>(4));
  for (__typeof(all.begin()) iter = all.begin(); iter != all.end(); ++iter) {
    string s = *iter;
    int me = index[s];
    for (int c = 0; c < 4; ++c) {
      char ch = CHARS[c];
      string ns = s + ch;
      while (all.count(ns) == 0) ns = ns.substr(1);
      next[me][c] = index[ns];
    }
  }
  vector<vector<int> > am(cnt, vector<int>(maxL, 0));
  am[index[""]][0] = 1;
  for (int i = 0; i < n; ++i) {
    vector<vector<int> > nam(cnt, vector<int>(maxL, 0));
    for (int oldState = 0; oldState < cnt; ++oldState) {
      for (int oldNeed = 0; oldNeed < maxL; ++oldNeed) {
        int cur = am[oldState][oldNeed];
        if (!cur) continue;
        for (int c = 0; c < 4; ++c) {
          int newState = next[oldState][c];
          int newNeed = oldNeed + 1;
          if (maxEnd[newState] >= newNeed) newNeed = 0;
          if (newNeed >= maxL) continue;
          nam[newState][newNeed] += cur;
          if (nam[newState][newNeed] >= MOD) nam[newState][newNeed] -= MOD;
        }
      }
    }
    am = nam;
  }
  int ans = 0;
  for (int i = 0; i < cnt; ++i) {
    (ans += am[i][0]) %= MOD;
  }
  cout << ans << endl;
}
