Fast DP algorithm implemented in C code
\nstatic const int64_t mod = 1000000007;\n\n/**\n * Calculates number of good strings alphabetically less or equal to s\n */\nint countGoodStrings(const char *s
```\nstatic const int64_t mod = 1000000007;\n\n/**\n * Calculates number of good strings alphabetically less or equal to s\n */\nint countGoodStrings(const char *s, const int n, const char* evil, const int el, const int64_t* dp) {\n    int64_t sum = 0;\n\n    int i, k;\n    for (i = 0; i <= n - el; ++i) {\n        for (k = 0; k < el && s[i + k] == evil[k]; ++k);\n        if (k == el) {\n            for (int j = i + k - 1; j >= i; --j) {\n                sum += (s[j] - \'a\') * dp[n - j - 1];\n                sum %= mod;\n            }\n            return sum - 1;\n        }\n        \n        if (s[i + k] < evil[k]) {\n            sum += (s[i] - \'a\') * dp[n - i - 1];\n        }\n        else {\n            sum += dp[n - i] - (\'z\' + 1 - s[i]) * dp[n - i - 1];\n        }\n        sum %= mod;\n    }\n\n    for (; i < n; ++i) {\n        sum += (s[i] - \'a\') * dp[n - i - 1];\n        sum %= mod;\n    }\n\n    return sum;\n}\n\nint findGoodStrings(int n, char * s1, char * s2, char * evil){\n    int el = strlen(evil);\n    int64_t *dp = (int64_t*)alloca((n + 1) * sizeof(int64_t));\n    memset(dp, 0, el * sizeof(int64_t));\n\n    // KMP algorithm\n    int k = 0, i = 1;\n    while (i < el) {\n        if (evil[k] == evil[i]) dp[i++] = ++k;\n        else if (k > 0) k = dp[k - 1];\n        else ++i;\n    }\n\n    k = el - dp[el - 1];\n\n    // dp[i]: total number of good strings of lenght i (\'a\' to \'z\')\n    // compute dp\n    dp[0] = 1LL;\n    for (i = 1; i < el; ++i) {\n        dp[i] = (dp[i - 1] * 26LL) % mod;\n    }\n\n    for (; i <= n; ++i) {\n        if (k == el) {\n            dp[i] = (dp[i - 1] * 26LL) % mod;\n            dp[i] -= dp[i - el];\n        }\n        else {\n            dp[i] = ((dp[i - 1] + dp[i - k - 1]) * 26LL) % mod;\n            dp[i] -= dp[i - el] + dp[i - k];\n        }\n    }\n\n    int res = countGoodStrings(s2, n, evil, el, dp) -\n              countGoodStrings(s1, n, evil, el, dp);\n    if (!strstr(s1, evil)) res++;\n    if (res < 0) res += mod;\n\n    return res % mod;\n}\n```
['C']