func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1E9 + 9;   int n, m, ans, cntNode(1),       root(1), f[200], dp[1005][105][13], vis[1005][105][13];   string s;   struct Trie {     int son[4], fail, len;     Trie() {       for (int i = 0; i < 4; i++) son[i] = 0;       fail = len = 0;     }   } tr[105];   void add(int& a, int b) { a = (a + b) % MOD; }   void insert(string& s) {     int cur = root;     for (int i = 0; i < s.size(); i++) {       if (!tr[cur].son[f[s[i]]]) tr[cur].son[f[s[i]]] = ++cntNode;       cur = tr[cur].son[f[s[i]]];     }     tr[cur].len = s.size();   }   void getFail() {     queue<int> Q;     Q.push(root);     tr[root].fail = root;     while (!Q.empty()) {       int now = Q.front();       Q.pop();       tr[now].len = max(tr[now].len, tr[tr[now].fail].len);       for (int i = 0; i < 4; i++) {         if (tr[now].son[i]) {           tr[tr[now].son[i]].fail = now != root ? tr[tr[now].fail].son[i] : root;           Q.push(tr[now].son[i]);         } else           tr[now].son[i] =               tr[tr[now].fail].son[i] ? tr[tr[now].fail].son[i] : root;       }     }   }   void DP() {     queue<tuple<int, int, int> > Q;     dp[0][1][0] = 1;     Q.push(make_tuple(0, 1, 0));     while (!Q.empty()) {       int len = get<0>(Q.front());       int node = get<1>(Q.front());       int last = get<2>(Q.front());       Q.pop();       if (len == n) {         if (!last) add(ans, dp[len][node][last]);         continue;       }       vis[len][node][last] = 0;       for (int i = 0; i < 4; i++) {         int to = tr[node].son[i];         int tmp = tr[to].len > last ? 0 : last + 1;         if (tmp > 10) continue;         add(dp[len + 1][to][tmp], dp[len][node][last]);         if (!vis[len + 1][to][tmp]) {           vis[len + 1][to][tmp] = 1;           Q.push(make_tuple(len + 1, to, tmp));         }       }     }     return;   }   signed main() {     ios::sync_with_stdio(false);     cin >> n >> m;     f[ A ] = 0, f[ T ] = 1, f[ C ] = 2, f[ G ] = 3;     for (int i = 1; i <= m; i++) cin >> s, insert(s);     getFail();     DP();     cout << ans;     return 0;   }   