func_code_string: #include <bits/stdc++.h>   using namespace std;   struct num {     static const int MA = 1e9 + 7, MB = 1e9 + 9;     int a, b;     num() {}     num(int x) : a(x), b(x) {}     num(int a, int b) : a(a), b(b) {}     num operator+(const num& x) const {       return num((a + x.a) % MA, (b + x.b) % MB);     }     num operator-(const num& x) const {       return num((a + MA - x.a) % MA, (b + MB - x.b) % MB);     }     num operator*(int x) const {       return num(((long long)a * x) % MA, ((long long)b * x) % MB);     }     num operator*(const num& x) const {       return num(((long long)a * x.a) % MA, ((long long)b * x.b) % MB);     }     bool operator==(const num& x) const { return a == x.a && b == x.b; }   };   struct num2 {     static const int MB = 1e9 + 9;     int b;     num2() {}     num2(int x) : b(x) {}     num2 operator+(const num2& x) const { return num2((b + x.b) % MB); }     num2 operator-(const num2& x) const { return num2((b + MB - x.b) % MB); }     num2 operator*(int x) const { return num2(((long long)b * x) % MB); }     num2 operator*(const num2& x) const {       return num2(((long long)b * x.b) % MB);     }     bool operator==(const num2& x) const { return b == x.b; }   };   const int MODP = 701;   template <class T>   struct StringOps {     StringOps() {}     StringOps(const string& s) : s(s) {       n = s.length();       deg.resize(n + 1);       hashes.resize(n);       deg[0] = T(1);       for (int i = 1; i <= n; ++i) {         deg[i] = deg[i - 1] * T(MODP);       }       T curhash = T(0);       for (int i = 0; i < n; ++i) {         curhash = curhash * T(MODP) + T(s[i]);         hashes[i] = curhash;       }     }     char get(int idx) { return s[idx]; }     T get_hash(int l, int r) {       T cur(0);       if (l > 0) {         cur = hashes[l - 1];       }       return hashes[r] - cur * deg[r - l + 1];     }     int string_lcp(int l, int r, int lim = 1e9) {       int cleft = 1, cright = min(n - r, n - l);       cright = min(lim, cright);       int res = 0;       while (cleft <= cright) {         int key = (cleft + cright) / 2;         if (s[l + key - 1] != s[r + key - 1]) {           cright = key - 1;         } else if (get_hash(l, l + key - 1) == get_hash(r, r + key - 1)) {           res = key;           cleft = key + 1;         } else {           cright = key - 1;         }       }       return res;     }     bool substring_cmp(int l1, int r1, int l2, int r2) {       int lcp = string_lcp(l1, l2);       int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;       if (lcp >= len1 && lcp >= len2) {         return len1 < len2;       }       if (lcp >= len1) {         return true;       }       if (lcp >= len2) {         return false;       }       return s[l1 + lcp] < s[l2 + lcp];     }     vector<T> hashes;     vector<T> deg;     string s;     int n;   };   const int maxN = 1000100;   const int MOD = 1e9 + 7;   int len1, len2;   int u, v;   StringOps<num2> sops;   int get_nlength(const pair<int, int>& a) {     if (a.first == u) {       if (a.second != len1) {         return len1 - 1;       } else {         return len1;       }     }     if (a.second != len2) {       return len2 - 1;     } else {       return len2;     }   }   void fill_segs(int& l1, int& r1, int& l2, int& r2, const pair<int, int>& a) {     if (a.first == u) {       l2 = r2 = -1;       if (a.second == 0) {         l1 = 1, r1 = len1 - 1;       } else if (a.second >= len1 - 1) {         l1 = 0, r1 = a.second - 1;       } else {         l1 = 0, r1 = a.second - 1;         l2 = a.second + 1, r2 = len1 - 1;       }       return;     }     l2 = r2 = -1;     if (a.second == 0) {       l1 = 1, r1 = len2 - 1;     } else if (a.second >= len2 - 1) {       l1 = 0, r1 = a.second - 1;     } else {       l1 = 0, r1 = a.second - 1;       l2 = a.second + 1, r2 = len2 - 1;     }     l1 += len1, r1 += len1;     if (l2 != -1) {       l2 += len1, r2 += len1;     }   }   int cmp2(vector<pair<int, int>>& a, vector<pair<int, int>>& b, int p1 = 0,            int p2 = 0) {     if (p1 == a.size() && p2 < b.size()) {       return -1;     }     if (p1 == a.size() && p2 == b.size()) {       return 0;     }     if (p2 == b.size() && p1 < a.size()) {       return 1;     }     if (p1 + 1 == a.size() && p2 + 1 == b.size() && a[0] == b[0]) {       return 0;     }     if (p1 + 2 == a.size() && p2 + 2 == b.size() && a[0] == b[0] &&         a[1] == b[1]) {       return 0;     }     if (sops.get(a[p1].first) != sops.get(b[p2].first)) {       char c1 = sops.get(a[p1].first);       char c2 = sops.get(b[p2].first);       if (c1 < c2) {         return -1;       }       return 1;     }     int lcp = sops.string_lcp(         a[p1].first, b[p2].first,         min(a[p1].second - a[p1].first + 1, b[p2].second - b[p2].first + 1));     lcp = min(         lcp, min(a[p1].second - a[p1].first + 1, b[p2].second - b[p2].first + 1));     int nx = a[p1].first + lcp - 1, ny = b[p2].first + lcp - 1;     if (nx >= a[p1].second) {       ++p1;     } else {       a[p1].first = nx + 1;     }     if (ny >= b[p2].second) {       ++p2;     } else {       b[p2].first = ny + 1;     }     return cmp2(a, b, p1, p2);   }   bool cmp(const pair<int, int>& a, const pair<int, int>& b) {     int nlen1 = get_nlength(a);     int nlen2 = get_nlength(b);     if (nlen1 == 0 && nlen2 == 0) {       if (a.first == u & b.first == v) {         return true;       }       return false;     }     if (nlen1 == 0) {       return true;     }     if (nlen2 == 0) {       return false;     }     int l1, r1, l2, r2;     fill_segs(l1, r1, l2, r2, a);     int p1, q1, p2, q2;     fill_segs(p1, q1, p2, q2, b);     vector<pair<int, int>> na;     vector<pair<int, int>> nb;     na.push_back(make_pair(l1, r1));     if (l2 != -1) {       na.push_back(make_pair(l2, r2));     }     nb.push_back(make_pair(p1, q1));     if (p2 != -1) {       nb.push_back(make_pair(p2, q2));     }     int val = cmp2(na, nb);     if (val == 0) {       if (a.first == u && b.first == v) {         return true;       }       return false;     }     return val == -1;   }   struct Node {     Node() { left = right = nullptr; }     int idxleft, idxright;     Node* left;     Node* right;   };   int curorder[maxN];   int lenorder;   void dfs(Node* root) {     if (!root) {       return;     }     if (root->left) {       dfs(root->left);     }     for (int i = root->idxleft; i <= root->idxright; ++i) {       curorder[lenorder] = i;       ++lenorder;     }     if (root->right) {       dfs(root->right);     }   }   pair<int, int> order[2][maxN];   int clen[2];   void get_order(const string& s, int p) {     int n = s.length();     Node* root = new Node();     Node* curnode = root;     for (int i = 0; i < n;) {       int cur = i;       while (cur < n && s[cur] == s[i]) {         ++cur;       }       curnode->idxleft = i, curnode->idxright = cur - 1;       if (cur == n) {         break;       }       if (s[i] < s[cur]) {         Node* left = new Node();         curnode->left = left;         curnode = curnode->left;       } else {         Node* right = new Node();         curnode->right = right;         curnode = curnode->right;       }       i = cur;     }     lenorder = 0;     dfs(root);     int ps = n;     for (int i = 0; i < n; ++i) {       if (curorder[i] == n - 1) {         ps = i + 1;         break;       }     }     vector<pair<int, int>> result;     clen[p] = 0;     for (int i = 0; i < ps; ++i) {       order[p][clen[p]] = make_pair(v, curorder[i]);       ++clen[p];     }     order[p][clen[p]] = make_pair(v, n);     ++clen[p];     for (int i = ps; i < n; ++i) {       order[p][clen[p]] = make_pair(v, curorder[i]);       ++clen[p];     }   }   int dp[2][maxN];   int dp2[2][maxN];   void gen() {     cout << 10 << endl;     for (int i = 0; i < 10; ++i) {       for (int j = 0; j < 100000; ++j) {         cout << char(rand() % 26 +  a );       }       cout << endl;     }   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     int n;     cin >> n;     vector<string> s(n);     for (int i = 0; i < n; ++i) {       cin >> s[i];     }     for (int i = 0; i <= s[0].length(); ++i) {       dp[u][i] = 1;       dp2[u][i] = 1;     }     sops = StringOps<num2>(s[0]);     len1 = 0, len2 = s[0].length();     u = 1, v = 0;     get_order(s[0], 0);     swap(u, v);     for (int i = 0; i + 1 < n; ++i) {       string& s1 = s[i];       string& s2 = s[i + 1];       string nw = s1 + s2;       len1 = s1.length(), len2 = s2.length();       sops = StringOps<num2>(nw);       get_order(s[i + 1], v);       int cadd = 0;       int head1 = 0, head2 = 0;       while (head1 < clen[u] || head2 < clen[v]) {         if (head1 == clen[u]) {           dp[v][order[v][head2].second] = cadd;           ++head2;         } else if (head2 == clen[v]) {           break;         } else {           if (cmp(order[u][head1], order[v][head2])) {             int nhead1 = head1;             while (nhead1 < clen[u] &&                    s1[order[u][nhead1].second] == s1[order[u][head1].second] &&                    order[u][nhead1].second - order[u][head1].second ==                        nhead1 - head1) {               ++nhead1;             }             for (int j = head1; j < nhead1; ++j) {               cadd += dp[u][order[u][j].second];               if (cadd >= MOD) {                 cadd -= MOD;               }             }             head1 = nhead1;           } else {             int nhead2 = head2;             while (nhead2 < clen[v] &&                    s2[order[v][nhead2].second] == s2[order[v][head2].second] &&                    order[v][nhead2].second - order[v][head2].second ==                        nhead2 - head2) {               ++nhead2;             }             for (int j = head2; j < nhead2; ++j) {               dp[v][order[v][j].second] = cadd;             }             head2 = nhead2;           }         }       }       swap(u, v);     }     int res = 0;     int res2 = 0;     for (int i = 0; i <= s.back().length(); ++i) {       res += dp[u][i];       if (res >= MOD) {         res -= MOD;       }       res2 += dp2[u][i];       if (res2 >= MOD) {         res2 -= MOD;       }     }     cout << res << endl;     cerr << (double)clock() / CLOCKS_PER_SEC << endl;     return 0;   }   