<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 {
// private:
//     int mod = 1e9+7;
//     unordered_map<long long int,unordered_map<long long int,long long int>> dp;
//     vector<vector<int>> charFreq;
//     int solve(int colIndex, int targetIndex, string target){
//         if(targetIndex==target.size())
//             return 1;
//         if(colIndex>=charFreq.size())
//             return 0;
//         if(dp[colIndex].count(targetIndex))
//             return dp[colIndex][targetIndex];
//         // dont take from this coloumn
//         long long int notTake = solve(colIndex+1, targetIndex, target);
//         // take from this coloumn
//         long long int take = 0;
//         int charIdx = target[targetIndex] - 'a';
//         if (charFreq[colIndex][charIdx] > 0) {
//             take = charFreq[colIndex][charIdx] * 1LL * solve(colIndex + 1, targetIndex + 1, target) % mod;
//         }
//         return dp[colIndex][targetIndex] = (notTake+take)%mod;
//     }
// public:
//     int numWays(vector<string>& words, string target) {
//         int m = words[0].size();
//         int n = words.size();
//         charFreq = vector<vector<int>>(m, vector<int>(26, 0));
//         for (int j = 0; j < m; ++j) {
//             for (int i = 0; i < n; ++i) {
//                 charFreq[j][words[i][j] - 'a']++;
//             }
//         }
//         return solve(0, 0, target);
//     }
// };

class Solution {
private:
    int mod = 1e9+7;
    unordered_map<long long, long long> dp; // Flattened dp map
    vector<vector<int>> charFreq;

    // Generate a unique key by combining colIndex and targetIndex
    long long getKey(int colIndex, int targetIndex) {
        return (static_cast<long long>(colIndex) << 32) | targetIndex;
    }

    int solve(int colIndex, int targetIndex, string& target) {
        if (targetIndex == target.size())
            return 1;
        if (colIndex >= charFreq.size())
            return 0;

        long long key = getKey(colIndex, targetIndex);
        if (dp.count(key))
            return dp[key];

        // Don't take from this column
        long long notTake = solve(colIndex + 1, targetIndex, target);

        // Take from this column
        long long take = 0;
        int charIdx = target[targetIndex] - 'a';
        if (charFreq[colIndex][charIdx] > 0) {
            take = charFreq[colIndex][charIdx] * 1LL * solve(colIndex + 1, targetIndex + 1, target) % mod;
        }

        dp[key] = (notTake + take) % mod;
        return dp[key];
    }

public:
    int numWays(vector<string>& words, string target) {
        int m = words[0].size();
        int n = words.size();
        charFreq = vector<vector<int>>(m, vector<int>(26, 0));

        // Precompute the frequency of each character in each column
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n; ++i) {
                charFreq[j][words[i][j] - 'a']++;
            }
        }

        return solve(0, 0, target);
    }
};

134428