<p>You are given a list of strings of the <strong>same length</strong> <code>words</code> and a string <code>target</code>.</p>

<p>Your task is to form <code>target</code> using the given <code>words</code> under the following rules:</p>

<ul>
	<li><code>target</code> should be formed from left to right.</li>
	<li>To form the <code>i<sup>th</sup></code> character (<strong>0-indexed</strong>) of <code>target</code>, you can choose the <code>k<sup>th</sup></code> character of the <code>j<sup>th</sup></code> string in <code>words</code> if <code>target[i] = words[j][k]</code>.</li>
	<li>Once you use the <code>k<sup>th</sup></code> character of the <code>j<sup>th</sup></code> string of <code>words</code>, you <strong>can no longer</strong> use the <code>x<sup>th</sup></code> character of any string in <code>words</code> where <code>x &lt;= k</code>. In other words, all characters to the left of or at index <code>k</code> become unusuable for every string.</li>
	<li>Repeat the process until you form the string <code>target</code>.</li>
</ul>

<p><strong>Notice</strong> that you can use <strong>multiple characters</strong> from the <strong>same string</strong> in <code>words</code> provided the conditions above are met.</p>

<p>Return <em>the number of ways to form <code>target</code> from <code>words</code></em>. Since the answer may be too large, return it <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> words = [&quot;acca&quot;,&quot;bbbb&quot;,&quot;caca&quot;], target = &quot;aba&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> There are 6 ways to form target.
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 1 (&quot;b<u>b</u>bb&quot;), index 3 (&quot;cac<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;cac<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 1 (&quot;b<u>b</u>bb&quot;), index 3 (&quot;acc<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 0 (&quot;<u>a</u>cca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;acc<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 1 (&quot;c<u>a</u>ca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;acc<u>a</u>&quot;)
&quot;aba&quot; -&gt; index 1 (&quot;c<u>a</u>ca&quot;), index 2 (&quot;bb<u>b</u>b&quot;), index 3 (&quot;cac<u>a</u>&quot;)
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;abba&quot;,&quot;baab&quot;], target = &quot;bab&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 ways to form target.
&quot;bab&quot; -&gt; index 0 (&quot;<u>b</u>aab&quot;), index 1 (&quot;b<u>a</u>ab&quot;), index 2 (&quot;ab<u>b</u>a&quot;)
&quot;bab&quot; -&gt; index 0 (&quot;<u>b</u>aab&quot;), index 1 (&quot;b<u>a</u>ab&quot;), index 3 (&quot;baa<u>b</u>&quot;)
&quot;bab&quot; -&gt; index 0 (&quot;<u>b</u>aab&quot;), index 2 (&quot;ba<u>a</u>b&quot;), index 3 (&quot;baa<u>b</u>&quot;)
&quot;bab&quot; -&gt; index 1 (&quot;a<u>b</u>ba&quot;), index 2 (&quot;ba<u>a</u>b&quot;), index 3 (&quot;baa<u>b</u>&quot;)
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 1000</code></li>
	<li>All strings in <code>words</code> have the same length.</li>
	<li><code>1 &lt;= target.length &lt;= 1000</code></li>
	<li><code>words[i]</code> and <code>target</code> contain only lowercase English letters.</li>
</ul>

class Solution {
public:
const int mod=1e9+7;
int bs(int s,vector<int> &arr){
    int start=0,end=arr.size()-1;
    int ans=-1;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(arr[mid]<s)start=mid+1;
        else{
            ans=mid;
            end=mid-1;
        }
    }
    if(ans==-1)return 0;
    return arr.size()-1-ans+1;
}
int bs_n(char ch,vector<int> &arr,int i){
    int start=0,end=arr.size()-1;
    int ans1=-1,ans2=-1;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(arr[mid]<i)start=mid+1;
        else if(arr[mid]>i)end=mid-1;
        else{
            ans1=mid;
            end=mid-1;
        }
    }
    start=0,end=arr.size()-1;
        while(start<=end){
        int mid=start+(end-start)/2;
        if(arr[mid]<i)start=mid+1;
        else if(arr[mid]>i)end=mid-1;
        else{
            ans2=mid;
            start=mid+1;
        }
    }
    if(ans1==-1)return 0;
    return ans2-ans1+1;
}
    int numWays(vector<string>& words, string target) {
        int ans=0;
        unordered_map<char,vector<int>> mp;
        for(auto i:words){
            for(int j=0;j<i.length();j+=1){
                mp[i[j]].push_back(j);
            }
        }
        for(int i='a';i<='z';i+=1){
            sort(mp[i].begin(),mp[i].end());
        }
        vector<vector<long long int>> dp(target.length(),vector<long long int>(words[0].length(),0));
        int curr=0;
                vector<vector<long long int>> pref(target.length(),vector<long long int>(words[0].length(),0));
        for(int i=0;i<words[0].length();i+=1){
            char ch=target[target.length()-1];
            int r=bs(i,mp[ch]);
            dp[dp.size()-1][i]=r;
            curr+=r;
            pref[dp.size()-1][i]=curr;
        }
        for(int i=target.length()-2;i>=0;i-=1){
            char ch=target[i];
            long long int curr=0;
            for(int j=words[0].length()-1;j>=0;j-=1){
                long long int cnt=bs_n(ch,mp[ch],j);
                if(j+1>=words[0].length())continue;
                if(i==target.length()-2)
                dp[i][j]=(cnt*dp[i+1][j+1])%mod;
                else dp[i][j]=(cnt*pref[i+1][j+1])%mod;
              //  cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<cnt<<endl;
                curr+=dp[i][j];
                pref[i][j]=curr;
            }
        }
        for(int i=0;i<words[0].length();i+=1){
            ans=(ans+dp[0][i])%mod;
        }
        return ans;
    }
};
112209