<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 numWays(vector<string>& words, string target) {
//         int n = target.size();
//         int mod = 1e9 + 7;
//         vector<long> result(n + 1);
//         result[0] = 1;
//         for (int i = 0; i < words[0].size(); ++i) {
//             array<int, 26> count{};
//             for (const auto& w : words) {
//                 ++count[w[i] - 'a'];
//             }
//             for (int j = n - 1; j >= 0; --j) {
//                 result[j + 1] += result[j] * count[target[j] - 'a'] % mod;
//             }
//         }
//         return result[n] % mod;
//     }
// };

// class Solution {
// public:
//     int numWays(vector<string>& A, string target) {
//         long mod = 1e9+7, M = A.size(), L = A[0].size(), N = target.size();
//         if (L < N) return 0;
//         vector<array<long, 26>> cnt(L, array<long, 26>());
//         for (int i = 0; i < L; ++i) {
//             for (int j = 0; j < M; ++j) cnt[i][A[j][i] - 'a']++;
//         }
//         vector<vector<int>> dp(L + 1, vector<int>(N + 1));
//         for (int i = 0; i < L; ++i) {
//             dp[i][0] = 1;
//             for (int j = 0; j <= i && j < N; ++j) {
//                 dp[i + 1][j + 1] = ((cnt[i][target[j] - 'a'] * dp[i][j]) % mod + dp[i][j + 1]) % mod;
//             }
//         }
//         return dp[L][N];
//     }
// };

// class Solution {
// public:
//     int numWays(vector<string>& words, string target) {
//         long mod = 1e9 + 7;
//         int word_size = words[0].size();
        
//         if (word_size < target.size()) {
//             return 0;
//         }
        
//         vector<array<long, 26>> cnt(word_size, array<long, 26>());
//         for (int i = 0; i < word_size; ++i) {
//             for (int j = 0; j < words.size(); ++j) {
//                 ++cnt[i][words[j][i] - 'a'];
//             }
//         }
        
//         vector<long> dp(target.size() + 1);
//         for (int i = 0; i < word_size; ++i) {
//             int prev = 1;
//             for (int j = 0; j <= i && j < target.size(); ++j) {
//                 int cur = dp[j + 1];
//                 dp[j + 1] = ((cnt[i][target[j] - 'a'] * prev) % mod + cur) % mod;
//                 prev = cur;
//             }
//         }
        
//         return dp[target.size()];
//     }
// };

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;

    int numWays(vector<string>& words, string target) {
        size_t n = target.size();
        vector<long> result(n + 1);
        result[0] = 1;

        for (size_t i = 0; i < words[0].size(); ++i) {
            int count[26]{};

            for (const auto& w : words) {
                ++count[w[i] - 'a'];
            }
            for (ptrdiff_t j = n - 1; j >= 0; --j) {
                result[j + 1] += count[target[j] - 'a'] * result[j] % MOD;
            }
        }
        return result[n] % MOD;
    }
};




32221