func_code_string: #include <bits/stdc++.h>   using namespace std;   string dna =  ACGT ;   string word[20];   set<string> words;   map<string, int> mp;   string pm[110];   pair<int, int> graph[110][20][4];   long long dp[1010][110][20];   int main() {     ios::sync_with_stdio(false);     int N, K, i, j, k, l, x;     cin >> N >> K;     for (i = 0; i < K; i++) cin >> word[i];     for (i = 0; i < K; i++) words.insert(word[i]);     for (i = 0; i < K; i++)       for (j = 1; j <= word[i].length(); j++) mp[word[i].substr(0, j)] = 0;     mp[  ] = 0;     int s = 0;     for (auto itr = mp.begin(); itr != mp.end(); itr++) {       (itr->second) = s;       pm[s] = (itr->first);       s++;     }     for (i = 0; i < s; i++) {       for (j = 0; j < pm[i].length() + 1; j++) {         for (k = 0; k < 4; k++) {           string s = pm[i] + dna[k];           int nextst = -1;           for (l = 0;; l++) {             if (mp.find(s.substr(l)) != mp.end()) {               nextst = mp[s.substr(l)];               break;             }           }           bool cover = false;           for (l = 0; l < pm[i].length() - j + 1; l++)             if (words.find(s.substr(l)) != words.end()) cover = true;           graph[i][j][k] = make_pair(-1, -1);           int nextcover = j + 1;           if (cover) nextcover = 0;           if (nextcover >= 10 || nextcover > pm[nextst].length()) continue;           graph[i][j][k] = make_pair(nextst, nextcover);         }       }     }     int start = mp[  ];     dp[0][start][0] = 1;     for (i = 0; i < N; i++) {       for (j = 0; j < s; j++) {         for (k = 0; k < 10; k++) {           if (dp[i][j][k] != 0) {             for (x = 0; x < 4; x++) {               pair<int, int> p = graph[j][k][x];               if (p.first != -1) {                 int i2 = i + 1, j2 = p.first, k2 = p.second;                 dp[i2][j2][k2] = (dp[i][j][k] + dp[i2][j2][k2]) % 1000000009ll;               }             }           }         }       }     }     long long ans = 0;     for (i = 0; i < s; i++) ans = (ans + dp[N][i][0]) % 1000000009ll;     cout << ans << endl;     return 0;   }   