func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MAXN = 1010, MAXM = 14, MAXS = MAXM * MAXM, MOD = 1e9 + 9;   void setmax(int &x, int y) {     if (x < y) {       x = y;     }   }   void add(int &x, int y) { x = (x + y) % MOD; }   int N, M;   string str[MAXM];   map<string, int> mp;   int ind;   int dp[MAXN][MAXS][MAXM];   int nxt[MAXS][4];   int suff[MAXS];   int main() {     if (fopen( input.txt ,  r )) {       freopen( input.txt ,  r , stdin);     }     ios::sync_with_stdio(false);     cin >> N >> M;     mp[  ] = ind++;     int maxlen = 0;     for (int i = 0; i < M; i++) {       cin >> str[i];       setmax(maxlen, str[i].length());       string t;       for (char c : str[i]) {         t += c;         if (!mp.count(t)) {           mp[t] = ind++;         }       }     }     for (auto it = (mp).begin(); it != (mp).end(); it++) {       string s;       for (int i = 0; i < 4; i++) {         s = it->first +  ACGT [i];         while (!mp.count(s)) {           s.erase(s.begin());         }         nxt[it->second][i] = mp[s];       }       s = it->first;       for (int i = 0; i < M; i++) {         string t = str[i];         if (s.length() < t.length()) {           continue;         }         bool match = true;         for (int i = int(s.length()) - 1, j = int(t.length()) - 1; j >= 0;              i--, j--) {           if (s[i] != t[j]) {             match = false;             break;           }         }         if (match) {           setmax(suff[it->second], t.length());         }       }     }     dp[0][0][0] = 1;     for (int i = 0; i < N; i++) {       for (int j = 0; j < ind; j++) {         for (int k = 0; k < maxlen; k++) {           for (int c = 0; c < 4; c++) {             int nj = nxt[j][c], nk = k + 1;             if (nk <= suff[nj]) {               nk = 0;             }             if (nk >= maxlen) {               continue;             }             add(dp[i + 1][nj][nk], dp[i][j][k]);           }         }       }     }     int ans = 0;     for (int i = 0; i < ind; i++) {       add(ans, dp[N][i][0]);     }     cout << ans << endl;   }   