<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:
    long long dp[501][2][2][51]; 
    long long N ; 
    string S1, S2, Evil ;
    long long mod = 1e9 + 7 ; 
    int helper(int cond, char ch){
        string s="";
        for(int i = 0 ; i < cond ; i++){
            s+=Evil[i]; 
        }
        s+=ch; 
        int res = 0 ; 
        for(int i = 0 ; i < s.size(); i++){
            int flag = 0 ; 
            int p1 = i ; 
            int p2 = 0; 
            while(p2 != Evil.size() and p1 < s.size()){
                if(s[p1] != Evil[p2]){
                    flag = 1 ; 
                    break ; 
                }
                p1++;
                p2++;
            }
            if(!flag){

                res = max(res, p2);
            }
        }
        // if(s.size() > 3){
        //     cout<<res<<endl;
        //     cout<<s<<endl;
        //     cout<<Evil<<endl<<endl;
            
        // }
        return res;
    }
    long long f( long long pos, long long lowerBound, long long UpperBound, long long cond){
        if(pos == N ){
            return 1 ; 
        }

        if( dp[pos][lowerBound][UpperBound][cond] != -1){
            return dp[pos][lowerBound][UpperBound][cond]; 
        }
        long long st = (lowerBound) ? S1[pos] -'a' : 0 ;
        // long long ed = UpperBound ? 25 : S1[pos] -'a';
        long long ed = (UpperBound) ? S2[pos]-'a' : 25 ;
        long long ans = 0 ; 
        // cout<<pos<<" "<<st<<" "<<ed<<" "<<endl;
        for(long long i = st ; i <= ed ; i++){
            if((cond + int(Evil[cond] == char(i + 'a')) ) == Evil.size() ){
                    // cout<<"here\n";
            }
            else if(Evil[cond] == char(i+'a')){
                ans+= f( pos+1,( lowerBound && i == st) , UpperBound && (i == ed) , cond+1);
            }
            else{
                int newCond = helper(cond, char(i+'a'));
               ans+= f( pos+1, lowerBound && i == st , UpperBound && (i == ed) , newCond);
                
            }
        }
        return dp[pos][lowerBound][UpperBound][cond] = ans %mod;

    }
    long long findGoodStrings(long long n, string s1, string s2, string evil) {
        
        N = n ; 
        S1 = s1; S2 = s2; Evil = evil ; 
             
        memset(dp , -1 , sizeof(dp));
        return f(0, 1, 1, 0);
    }
};
41600