<p>Given the strings <code>s1</code> and <code>s2</code> of size <code>n</code> and the string <code>evil</code>, return <em>the number of <strong>good</strong> strings</em>.</p>

<p>A <strong>good</strong> string has size <code>n</code>, it is alphabetically greater than or equal to <code>s1</code>, it is alphabetically smaller than or equal to <code>s2</code>, and it does not contain the string <code>evil</code> as a substring. Since the answer can be a huge number, return this <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;aa&quot;, s2 = &quot;da&quot;, evil = &quot;b&quot;
<strong>Output:</strong> 51 
<strong>Explanation:</strong> There are 25 good strings starting with &#39;a&#39;: &quot;aa&quot;,&quot;ac&quot;,&quot;ad&quot;,...,&quot;az&quot;. Then there are 25 good strings starting with &#39;c&#39;: &quot;ca&quot;,&quot;cc&quot;,&quot;cd&quot;,...,&quot;cz&quot; and finally there is one good string starting with &#39;d&#39;: &quot;da&quot;.&nbsp;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 8, s1 = &quot;leetcode&quot;, s2 = &quot;leetgoes&quot;, evil = &quot;leet&quot;
<strong>Output:</strong> 0 
<strong>Explanation:</strong> All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix &quot;leet&quot;, therefore, there is not any good string.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2, s1 = &quot;gx&quot;, s2 = &quot;gz&quot;, evil = &quot;x&quot;
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>s1.length == n</code></li>
	<li><code>s2.length == n</code></li>
	<li><code>s1 &lt;= s2</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= evil.length &lt;= 50</code></li>
	<li>All strings consist of lowercase English letters.</li>
</ul>

class Solution {
public:
    #define mod 1000000007
    int dp[501][53][2];
    string_view s, ev;

    int dp2[51][26];

    int next(int ind, char c) {
        int &ret = dp2[ind][c - 'a'];
        if(ret != -1) return ret;
        // not found
        string t = string(ev.substr(0, ind)) + c;
        string_view tt = t;
        tt = tt.substr(1);
        while(!tt.empty()) {
            if(ev.substr(0, tt.size()) == tt) return ret = tt.size();
            tt = tt.substr(1);
        }
        return ret = 0;
    }

    int rec(int i, int inde, bool hitight) {
        if(inde == ev.size()) return 0;
        if(i >= s.size()) return 1;
        int &ret = dp[i][inde][hitight];
        if(ret != -1) return ret;
        // not found

        long ans = 0;

        for(int a = 0; a < 26; ++a) {
            char c = a + 'a';
            if(hitight && c > s[i]) continue;

            bool nexthi = hitight && c == s[i];
            if(inde == 0) {  // not start evil yet
                if(c == ev[inde]) {
                    ans += rec(i + 1, 1, nexthi);
                }
                else {
                    ans += rec(i + 1, 0, nexthi);
                }
            } else { // need to keep evil
                if(c == ev[inde])
                    ans += rec(i + 1, inde + 1, nexthi);
                else {
                    // ans += rec(i + 1, 0, nexthi);  // should not restart
                    int restart_point = next(inde, c);
                    ans += rec(i + 1, restart_point, nexthi);
                }
            }
        }
        return ret = ans % mod;
    }

    inline bool alla(string_view s) {
        for(char c: s) if(c != 'a')
            return false;
        return true;
    }

    inline bool contains(string_view a, string_view b) {
        int k = a.size() - b.size() + 1;
        for(int i = 0; i < k; ++i) {
            if(a.substr(i, b.size()) == b) return true;
        }
        return false;
    }

    int findGoodStrings(int n, string s1, string s2, string evil) {
        s = s2, ev = evil;
        memset(dp, -1, sizeof(dp));
        memset(dp2, -1, sizeof(dp2));

        long LEs2_withoutEV = rec(0, 0, true);

        s = s1, ev = evil;
        memset(dp, -1, sizeof(dp));

        long LEs1 = rec(0, 0, true);

        return (LEs2_withoutEV - LEs1 + !contains(s1, evil) + mod) % mod;
    }
};
11600