func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1000000009;   const int MAXN = 128;   const int MAXK = 4;   struct TrieNode {     int next[MAXK], fail;     int danger;     void init() {       fail = -1;       danger = 0;       for (int i = 0; i < MAXK; ++i) next[i] = -1;     }   } T[MAXN];   int root, Top;   void Init() {     root = 0, Top = 1;     T[root].init();   }   int GetId(char ch) {     switch (ch) {       case  A :         return 0;       case  G :         return 1;       case  C :         return 2;       case  T :         return 3;     }   }   void TrieIns(char *s) {     int i = 0;     int p = root;     while (s[i]) {       int idx = GetId(s[i]);       if (T[p].next[idx] == -1) {         T[Top].init();         T[p].next[idx] = Top++;       }       p = T[p].next[idx];       i++;     }     T[p].danger = strlen(s);   }   void Build_AC_Automation() {     int cur, tmp;     queue<int> q;     T[root].fail = root;     T[root].danger = 0;     q.push(root);     while (!q.empty()) {       cur = q.front();       q.pop();       for (int i = 0; i < MAXK; ++i) {         if (T[cur].next[i] != -1) {           tmp = T[cur].next[i];           if (cur == root)             T[tmp].fail = root;           else {             T[tmp].fail = T[T[cur].fail].next[i];             T[tmp].danger = max(T[tmp].danger, T[T[tmp].fail].danger);           }           q.push(tmp);         } else {           if (cur == root)             T[cur].next[i] = root;           else             T[cur].next[i] = T[T[cur].fail].next[i];         }       }     }   }   long long dp[1010][128][11];   int n, m;   int main() {     memset(dp, 0, sizeof(dp));     cin >> n >> m;     Init();     for (int i = 0; i < m; ++i) {       char str[20];       cin >> str;       TrieIns(str);     }     Build_AC_Automation();     dp[0][0][0] = 1;     for (int i = 0; i < n; ++i) {       for (int j = 0; j < Top; ++j) {         for (int k = 0; k <= 10; ++k) {           if (dp[i][j][k] == 0) continue;           for (int t = 0; t < MAXK; ++t) {             int aa = T[j].next[t];             if (T[aa].danger > k) {               dp[i + 1][aa][0] += dp[i][j][k];               dp[i + 1][aa][0] %= MOD;             } else if (k + 1 <= 10) {               dp[i + 1][aa][k + 1] += dp[i][j][k];               dp[i + 1][aa][k + 1] %= MOD;             }           }         }       }     }     long long ans = 0;     for (int i = 0; i < Top; ++i) {       ans = ans + dp[n][i][0];       ans %= MOD;     }     cout << ans % MOD << endl;   }   