<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>

r'''
# Requirements

n = len(words), t = len(target)
m = len(words[i])
1 <= n <= 1000
1 <= t, m <= 1000
words[i][j], target[i] is a-z
words[i] in words have the same length

# Edge cases

1. m < t
    - Cannot form target, return 0
2. No ways to form target

# Solutions

1. Brute force, backtracking
    - O(n^m) time, O(m) auxiliary space
2. Hash map / integer array + memoization / DP
    - O(mt) time, O(mt) auxiliary space
2. Hash map / integer array + DP, space optimized
    - O(mt) time, O(m + t) auxiliary space
'''
MOD = 10 ** 9 + 7

def prepare_frequency_lists(words: list[str]) -> list[int]:
    m = len(words[0])
    freqs = [[0] * 26 for _ in range(m)]

    for word in words:
        for i in range(m):
            code = ord(word[i]) - ord('a')
            freqs[i][code] += 1

    return freqs

def ways_to_form_word_memo(words: list[str], target: str) -> int:
    m, t = len(words[0]), len(target)

    # Edge case: words are not long enough to form target
    if m < t:
        return 0

    # DP
    freqs = prepare_frequency_lists(words)

    @lru_cache(maxsize = (m + 1) * (t + 1))
    def ways_to_form_word(picked: int, i: int) -> int:
        if picked == t:
            return 1
        if i == m:
            return 0

        want = ord(target[picked]) - ord('a')
        ways = ways_to_form_word(picked, i + 1) % MOD

        if freqs[i][want] > 0:
            ways = (ways + freqs[i][want] * ways_to_form_word(picked + 1, i + 1)) % MOD

        return ways

    return ways_to_form_word(0, 0)

def ways_to_form_word_dp(words: list[str], target: str) -> int:
    m, t = len(words[0]), len(target)

    # Edge case: words are not long enough to form target
    if m < t:
        return 0

    # DP
    freqs = prepare_frequency_lists(words)

    dp1 = [0] * (t + 1)
    dp1[t] = 1

    for i in range(m - 1, -1, -1):
        dp0 = [0] * (t + 1)
        dp0[t] = 1

        for picked in range(t - 1, -1, -1):
            want = ord(target[picked]) - ord('a')
            dp0[picked] = (dp1[picked] + freqs[i][want] * dp1[picked + 1]) % MOD
        dp1 = dp0

    return dp1[0]

class Solution:
    def numWays(self, words: list[str], target: str) -> int:
        return ways_to_form_word_dp(words, target)
25531