<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:
    int n;
    int m;
    int t[1001][1001];
    const int MOD = 1e9+7;
    // int solve(int i ,int j ,string &target ,vector<vector<long long>>& freq){
    //     if(i == n)
    //     return 1;
        
    //     if(j == m)
    //     return 0;

    //     if(t[i][j] != -1)
    //      return t[i][j];

    //     int not_taken = (solve(i,j+1,target,freq))%MOD;
    //     int taken = (freq[target[i] -'a'][j] * solve(i+1,j+1,target,freq))%MOD;

    //     return t[i][j] = (not_taken + taken)%MOD;
    // }
    int numWays(vector<string>& words, string target) {
        n = target.length();
        m = words[0].size();
         

        vector<vector<long long>> freq(26, vector<long long>(m));
        for(int col = 0 ;col < m; col++){
            for(string &word : words){
                // char ch = word[col];
                // freq[ch - 'a'][col]++;
                 freq[word[col] - 'a'][col]++;
            }
        }
          vector<vector<long long>> dp(n+1,vector<long long>(m+1));
          dp[0][0] = 1;
          
          for(int i = 0 ;i<=n;i++){
            for(int j = 0; j<=m;j++){
                // not takint case
                if(j<m)
                dp[i][j+1] = (dp[i][j+1] + dp[i][j])%MOD;

                if(i<n && j<m)
                dp[i+1][j+1] = (dp[i+1][j+1] + freq[target[i]-'a'][j]*dp[i][j])%MOD;
            }
          }
          return dp[n][m];
    }
};

// class Solution {
// public:
//     int n;
//     int m;
//     int t[1001][1001];
//     const int MOD = 1e9+7;
//     int solve(int i ,int j ,string &target ,vector<vector<long long>>& freq){
//         if(i == n)
//         return 1;
        
//         if(j == m)
//         return 0;

//         if(t[i][j] != -1)
//          return t[i][j];

//         int not_taken = (solve(i,j+1,target,freq))%MOD;
//         int taken = (freq[target[i] -'a'][j] * solve(i+1,j+1,target,freq))%MOD;

//         return t[i][j] = (not_taken + taken)%MOD;
//     }
//     int numWays(vector<string>& words, string target) {
//         n = target.length();
//         m = words[0].size();
         

//         vector<vector<long long>> freq(26, vector<long long>(m));
//         for(int col = 0 ;col < m; col++){
//             for(string &word : words){
//                 // char ch = word[col];
//                 // freq[ch - 'a'][col]++;
//                  freq[word[col] - 'a'][col]++;
//             }
//         }
//           memset(t,-1,sizeof(t));
//         return solve(0,0,target,freq);
//     }
// };
89990