func_code_string: #include <bits/stdc++.h>   using namespace std;   const int INF = 0x3fffffff;   const int SINF = 0x7fffffff;   const long long LINF = 0x3fffffffffffffff;   const long long SLINF = 0x7fffffffffffffff;   const int MAXN = 1007;   const int MAXS = 107;   const int MAXM = 13;   const int MAXL = 13;   const int BASE = 4;   const int MOD = 1e9 + 9;   int toid[128];   int n, m, kn, ml;   char s[MAXM][MAXL];   int nxt[MAXS][BASE], fail[MAXS], q[MAXS];   int ok[MAXS];   int tag[MAXS];   int dp[MAXN][MAXL][MAXS];   void init();   void input();   void work();   void trie_add(char s[]);   void buildac();   int main() {     init();     input();     work();   }   void init() {     ios::sync_with_stdio(false);     toid[ A ] = 0;     toid[ C ] = 1;     toid[ G ] = 2;     toid[ T ] = 3;   }   void input() {     scanf( %d%d , &n, &m);     for (int i = 0; i < m; ++i) scanf( %s , s[i]);   }   void work() {     kn = 1;     memset(nxt, -1, sizeof(nxt));     memset(tag, 0, sizeof(tag));     for (int i = 0; i < m; ++i)       trie_add(s[i]), ml = (((ml) > (strlen(s[i]))) ? (ml) : (strlen(s[i])));     buildac();     ++ml;     memset(dp, 0, sizeof(dp));     dp[0][0][0] = 1;     int v, nj, nl;     for (int i = 0; i < n; ++i) {       for (int j = 0; j < ml; ++j) {         for (int k = 0; k < kn; ++k) {           if (dp[i][j][k]) {             for (int nc = 0; nc < BASE; ++nc) {               v = nxt[k][nc];               nj = j + 1;               if (tag[v] || ok[v]) {                 if (tag[v])                   nl = tag[v];                 else                   nl = tag[ok[v]];                 if (nl >= nj) nj = 0;               }               dp[i + 1][nj][v] += dp[i][j][k];               dp[i + 1][nj][v] %= MOD;             }           }         }       }     }     int sum = 0;     for (int i = 0; i < kn; ++i) {       sum += dp[n][0][i];       sum %= MOD;     }     printf( %d n , sum);   }   void trie_add(char s[]) {     int len = strlen(s), now = 0, nc;     for (int i = 0; i < len; ++i) {       nc = toid[s[i]];       if (nxt[now][nc] ^ -1)         now = nxt[now][nc];       else         now = nxt[now][nc] = kn++;     }     tag[now] = len;   }   void buildac() {     int l = 0, r = 0, now, v, f;     q[r++] = 0;     fail[0] = 0;     while (l < r) {       now = q[l++];       for (int i = 0; i < BASE; ++i) {         if (nxt[now][i] ^ -1) {           v = nxt[now][i];           q[r++] = v;           f = fail[now];           while (f && nxt[f][i] == -1) f = fail[f];           fail[v] = (now && nxt[f][i] ^ -1) ? nxt[f][i] : 0;         } else           nxt[now][i] = (nxt[fail[now]][i] ^ -1) ? nxt[fail[now]][i] : 0;       }       f = fail[now];       while (f && !tag[f]) f = ok[f];       ok[now] = f;     }   }   