#include <bits/stdc++.h>   using namespace std;   const int maxn = 1500;   const int MOD = 1e9 + 9;   int ing[128];   long long dp[1005][105][15];   int n, m;   struct ac_auto {     int nxt[maxn][4], fail[maxn], ed[maxn], q[maxn];     int L = 0;     void inserta(char buf[]) {       int now = 0;       int len = strlen(buf);       for (int i = 0; buf[i]; i++) {         int son = ing[(int)buf[i]];         if (!nxt[now][son]) nxt[now][son] = ++L;         now = nxt[now][son];       }       ed[now] = len;     }     void getfail() {       int front = 0, back = 0, now = 0;       for (int i = 0; i < 4; i++)         if (nxt[now][i]) q[++back] = nxt[now][i];       while (front < back) {         now = q[++front];         for (int i = 0; i < 4; i++) {           if (nxt[now][i]) {             fail[nxt[now][i]] = nxt[fail[now]][i];             q[++back] = nxt[now][i];           } else             nxt[now][i] = nxt[fail[now]][i];           ed[nxt[now][i]] = max(ed[nxt[now][i]], ed[nxt[fail[now]][i]]);         }       }     }     void work() {       memset(dp, 0, sizeof dp);       dp[0][0][0] = 1;       for (int i = 0; i < n; i++) {         for (int j = 0; j <= L; j++) {           for (int k = 0; k <= 10; k++)             for (int f = 0; f < 4; f++) {               if (ed[nxt[j][f]] > k) {                 dp[i + 1][nxt[j][f]][0] += dp[i][j][k];                 dp[i + 1][nxt[j][f]][0] %= MOD;               } else {                 dp[i + 1][nxt[j][f]][k + 1] += dp[i][j][k];                 dp[i + 1][nxt[j][f]][k + 1] %= MOD;               }             }         }       }       long long ans = 0;       for (int i = 0; i <= L; i++) {         ans += dp[n][i][0];         ans %= MOD;       }       cout << ans << endl;     }   } ac;   char ss[15];   int main() {     ing[ A ] = 0, ing[ T ] = 1, ing[ C ] = 2, ing[ G ] = 3;     scanf( %d%d , &n, &m);     for (int i = 1; i <= m; i++) {       scanf( %s , ss);       ac.inserta(ss);     }     ac.getfail();     ac.work();     return 0;   }   