#include <bits/stdc++.h>
using namespace std;
long n, m;
vector<string> pref;
long mov[500][500];
string temp;
string inp[500];
long er, td;
long bst[2000];
string tst;
long dp[4][500][500];
long nend, t, ncvrd, answ;
void ad(long &a, long b) {
  a += b;
  if (a >= 1000000009) a -= 1000000009;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> inp[i];
    for (int j = 0; j < inp[i].size(); j++) inp[i][j] = inp[i][j] - 'A' + 'a';
  }
  pref.push_back("");
  for (int i = 1; i <= m; i++) {
    temp = "";
    for (int j = 0; j < inp[i].size(); j++) {
      temp += inp[i][j];
      pref.push_back(temp);
    }
  }
  for (int i = 0; i < pref.size(); i++) {
    bst[i] = -1;
    for (int j = 1; j <= m; j++) {
      if (inp[j].size() > pref[i].size()) continue;
      er = 0;
      if (bst[i] >= 0 && inp[j].size() <= inp[bst[i]].size()) continue;
      td = pref[i].size() - inp[j].size();
      for (int q = 0; q < inp[j].size(); q++)
        if (pref[i][q + td] != inp[j][q]) {
          er = 1;
          break;
        }
      if (er == 0) bst[i] = j;
    }
  }
  for (int i = 0; i < pref.size(); i++)
    for (int ad = 0; ad < 26; ad++) {
      mov[i][ad] = -1;
      tst = pref[i];
      tst += char('a' + ad);
      for (int j = 0; j < pref.size(); j++) {
        if (pref[j].size() > tst.size()) continue;
        er = 0;
        td = tst.size() - pref[j].size();
        if (mov[i][ad] != -1 && pref[mov[i][ad]].size() > pref[j].size())
          continue;
        for (int q = 0; q < pref[j].size(); q++)
          if (pref[j][q] != tst[td + q]) {
            er = 1;
            break;
          }
        if (er == 0) mov[i][ad] = j;
      }
    }
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= pref.size(); j++)
      for (int q = 0; q <= i; q++) dp[1 - i % 2][j][q] = 0;
    for (int end = 0; end < pref.size(); end++)
      for (int cvrd = 0; cvrd <= i; cvrd++)
        if (cvrd >= i - 25)
          if (dp[i % 2][end][cvrd])
            for (int achar = 0; achar < 26; achar++) {
              nend = mov[end][achar];
              t = bst[nend];
              if (t > -1 && inp[t].size() + cvrd > i)
                ncvrd = i + 1;
              else
                ncvrd = cvrd;
              ad(dp[1 - i % 2][nend][ncvrd], dp[i % 2][end][cvrd]);
            }
  }
  answ = 0;
  for (int end = 0; end < pref.size(); end++) ad(answ, dp[n % 2][end][n]);
  cout << answ << endl;
  cin.get();
  cin.get();
  return 0;
}
