Dp on digits and kmp
\n#define ll long long\nconst int Mxn = 505;\n\nclass Solution {\npublic:\n    \n    int mod = 1e9 + 7;\n    int N, M;\n    string _s1, _s2, _evil;\n    ll dp[M
```\n#define ll long long\nconst int Mxn = 505;\n\nclass Solution {\npublic:\n    \n    int mod = 1e9 + 7;\n    int N, M;\n    string _s1, _s2, _evil;\n    ll dp[Mxn][2][2][Mxn];\n    int pat[Mxn];\n    \n    void build() {\n        int j = 0;\n        for(int i = 1; i < M; i++) {\n            while(j > 0 && _evil[i] != _evil[j]) j = pat[j-1];\n            if(_evil[i] == _evil[j]) j++;\n            pat[i] = j;\n        }\n    }\n    \n    int next(int p, int j) {\n        char c = char(\'a\' + j);\n        while(p > 0 && _evil[p] != c) p = pat[p-1];\n        if(_evil[p] == c) p++;\n        return p;\n    }\n    \n    ll go(int i, int ba, int tb, int p) {\n        if(p == M) return 0;\n        if(i == N) return 1;\n        ll & ans = dp[i][ba][tb][p];\n        if(ans == -1) {\n            ans = 0;\n            int top = tb ? _s2[i]-\'a\' : 25;\n            int bot = ba ? _s1[i]-\'a\' : 0;\n            for(int j = bot; j <= top; j++) {\n                ans = (ans + \n                       go(i+1, ba && j == bot, tb && j == top, next(p, j))) % mod;\n            }\n        }\n        return ans;\n    }\n    \n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        N = n, M = evil.size();\n        _s1 = s1, _s2 = s2, _evil = evil;\n        build();\n        memset(dp, -1, sizeof dp);\n        return go(0, 1, 1, 0);\n    }\n};\n```
[]