<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>

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;

class Solution {
public:
    int dp[501][2][2][51];
    int genv(int ind,int tight1,int tight2,string &s1,string &s2,vector<vector<int>> &pos,int seen,int n)
    {
        if(seen==n)
        {
            return 0;
        }

        if(ind==s1.size())
        {
            return 1;
        }

        if(dp[ind][tight1][tight2][seen]!=-1)
        {
            return dp[ind][tight1][tight2][seen];
        }

        int ans=0;
        if(tight1==1 && tight2==0)
        {
           for(int j=0;j<26;j++)
           {
             char c='a'+j;
             if(c<s2[ind])
             {
                ans=(ans+genv(ind+1,tight1,1,s1,s2,pos,pos[seen][j],n))%mod;
             }
             else if(c==s2[ind])
             {
                ans=(ans+genv(ind+1,tight1,tight2,s1,s2,pos,pos[seen][j],n))%mod;
             }
           }
        }
        else if(tight1==0 && tight2==1)
        {
           for(int j=0;j<26;j++)
           {
            char c='a'+j;
            if(c>s1[ind])
            {
              ans=(ans+genv(ind+1,1,tight2,s1,s2,pos,pos[seen][j],n))%mod;
            }
            else if(c==s1[ind])
            {
                ans=(ans+genv(ind+1,0,tight2,s1,s2,pos,pos[seen][j],n))%mod;
            }
           }
        }
        else if(tight1==1 && tight2==1)
        {
          for(int j=0;j<26;j++)
          {
            ans=(ans+genv(ind+1,tight1,tight2,s1,s2,pos,pos[seen][j],n))%mod;
          }
        }
        else if(tight1==0 && tight2==0)
        {
          for(int j=0;j<26;j++)
          {
            char c='a'+j;
            if(c>s1[ind])
            {
               if(c<s2[ind])
               {
                ans=(ans+genv(ind+1,1,1,s1,s2,pos,pos[seen][j],n))%mod;
               }
               else if(c==s2[ind])
               {
               ans=(ans+genv(ind+1,1,0,s1,s2,pos,pos[seen][j],n))%mod;
               }
            }
            else if(c==s1[ind])
            {
               if(c<s2[ind])
               {
                ans=(ans+genv(ind+1,0,1,s1,s2,pos,pos[seen][j],n))%mod;
               }
               else if(c==s2[ind])
               {
                ans=(ans+genv(ind+1,0,0,s1,s2,pos,pos[seen][j],n))%mod;
               }
            }
          }
        }

        return dp[ind][tight1][tight2][seen]=ans;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) 
    {
        int evils=evil.size();
        vector<vector<int>> pos(n+1,vector<int>(26,0));
        for(int i=0;i<=evils;i++)
        {
            if(i==n)
            {
                break;
            }
            string s="";
            if(i==0)
            {

            }
            else
            {
                s=evil.substr(0,i);
            }

            for(int j=0;j<26;j++)
            {
                if(evil[i]==('a'+j))
                {
                    pos[i][j]=i+1;
                }
                else
                {
                    s+=('a'+j);
                    int maxi=-1;
                    int x=s.size();
                    x--;
                    for(int k=0;k<=x;k++)
                    {
                        int f=0;
                        int cnt=x;
                        for(int k1=k;k1>=0;k1--)
                        {
                            if(s[cnt]==evil[k1])
                            {

                            }
                            else
                            {
                                f=1;
                                break;
                            }
                            cnt--;
                        }
                        if(f==1)
                        {

                        }
                        else
                        {
                            maxi=max(maxi,k);
                        }
                    }
                    s.pop_back();
                    pos[i][j]=maxi+1;
                }

            }

        }
        memset(dp,-1,sizeof(dp));
        return genv(0,0,0,s1,s2,pos,0,evils);
    }
};  

9400