func_code_string: #include <bits/stdc++.h>   using namespace std;   long long n, m, k;   long long read() {     long long s = 0, f = 1;     char ch = getchar();     while (ch <  0  || ch >  9 ) {       if (ch ==  - ) f = -1;       ch = getchar();     }     while (ch >=  0  && ch <=  9 ) {       s = s * 10 + ch -  0 ;       ch = getchar();     }     return s * f;   }   long long cnt = 0;   struct trie {     long long ch[26];     long long fail;     long long tail;   } t[10010];   long long f(char c) {     if (c ==  A ) return 0;     if (c ==  C ) return 1;     if (c ==  T )       return 2;     else       return 3;   }   void insert(string s) {     long long l = s.size();     long long nw = 0;     for (long long i = 0, iend = l - 1; i <= iend; ++i) {       if (t[nw].ch[f(s[i])] == 0) {         t[nw].ch[f(s[i])] = ++cnt;       }       nw = t[nw].ch[f(s[i])];     }     t[nw].tail = l;   }   void bfs() {     queue<long long> q;     for (long long i = 0, iend = 25; i <= iend; ++i) {       if (t[0].ch[i]) {         t[t[0].ch[i]].fail = 0;         q.push(t[0].ch[i]);       }     }     while (!q.empty()) {       long long nw = q.front();       q.pop();       for (long long i = 0, iend = 25; i <= iend; ++i) {         if (t[nw].ch[i] != 0) {           t[t[nw].ch[i]].fail = t[t[nw].fail].ch[i];           t[t[nw].ch[i]].tail =               max(t[t[nw].ch[i]].tail, t[t[t[nw].ch[i]].fail].tail);           q.push(t[nw].ch[i]);         } else {           t[nw].ch[i] = t[t[nw].fail].ch[i];         }       }     }   }   const long long inf = 1e16;   long long dp[1010][1010][11];   const long long mod = 1e9 + 9;   signed main() {     n = read(), m = read();     long long l = 0;     for (long long i = 1, iend = m; i <= iend; ++i) {       string s;       cin >> s;       long long ss = s.size();       l = max(l, ss);       insert(s);     }     bfs();     dp[0][0][0] = 1;     for (long long i = 0, iend = n - 1; i <= iend; ++i) {       for (long long j = 0, jend = cnt; j <= jend; ++j) {         long long v;         for (long long k = 0, kend = l; k <= kend; ++k) {           v = dp[i][j][k];           if (v) {             for (long long p = 0, pend = 3; p <= pend; ++p) {               long long nw = t[j].ch[p];               if (t[nw].tail > k)                 (dp[i + 1][nw][0] += v) %= mod;               else if (k < l)                 (dp[i + 1][nw][k + 1] += v) %= mod;             }           }         }       }     }     long long ans = 0;     for (long long i = 0, iend = cnt; i <= iend; ++i) {       (ans += dp[n][i][0]) %= mod;     }     cout << ans;   }   