<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:
    def numWays(self, words: List[str], target: str) -> int:
        return self._sol2(words, target)

    def _sol2(self, words: List[str], target: str) -> int:
        MOD = 1_000_000_007
        n = len(words[0])
        m = len(target)
        char_pos_counts = [collections.defaultdict(int) for _ in range(n)]
        for w in words:
            for i, c in enumerate(w):
                char_pos_counts[i][c] += 1
        @cache
        def num_ways(i: int, j: int) -> int:
            if j == m:
                return 1
            if n - i < m - j:
                return 0
            # Add the ways if we don't use any character from this i position
            count = num_ways(i + 1, j)
            # And the ways we can use the right character at this i position
            if target[j] in char_pos_counts[i]:
                count += char_pos_counts[i][target[j]] * num_ways(i + 1, j + 1)
            return count % MOD
        return num_ways(0, 0)











































    # Working on test cases (succeeded on 84 out of 90) but timed out on the 85th
    # Perf: 93.3% 671 ms, 52.8% 108.0 mb. Only change I had to make was storing a count of chars at each index, then just multiplying.
    #   Ended up with a good solution but really should have done that in the first place.
    def _sol1(self, words: List[str], target: str) -> int:
        word_len = len(words[0])
        targ_len = len(target)
        if targ_len > word_len:
            return 0
        chars_by_index = [collections.defaultdict(int) for _ in range(word_len)]
        for word in words:
            for i in range(word_len):
                chars_by_index[i][word[i]] += 1
        memo = {}
        for i in range(word_len + 1):
            memo[(i, targ_len)] = 1 # If we've processed the whole string, that's a success
        def helper(next_word_i: int, targ_i: int) -> int:
            if (next_word_i, targ_i) not in memo:
                running_sum = 0
                for char, count in chars_by_index[next_word_i].items():
                    if char == target[targ_i]:
                        running_sum += count * helper(next_word_i + 1, targ_i + 1)
                if word_len - next_word_i > targ_len - targ_i:
                    # We can try to skip taking a letter from this next_word_i
                    running_sum += helper(next_word_i + 1, targ_i)
                memo[(next_word_i, targ_i)] = running_sum
            return memo[(next_word_i, targ_i)]
        return helper(0, 0) % 1_000_000_007
        
521