You are given a list of $n$ strings, words, where each string has the same length $m$, and a target string, target, of length $t$. A target can be formed using the given words under the following rules:

• You must build the target from left to right.

• To form the ith character (0-indexed) of target, you can choose any kth character of any jth string in words, i.e., target[i] = words[j][k].

• Once you use the kth character of the jth string in words, your next letter can't be a character from index $0$ through k of any string in words. In simple words, all characters to the left of or at index k become unusable for every string, and the next letter must come from positions strictly to the right of k.

• Repeat the process until you’ve formed the complete target.

Note: You can use multiple characters from the same string in words, as long as the rules above are followed.

Your task is to find and return the number of ways to form the string target from words. As the answer might be too large, return it modulo $10^{9} + 7$.

Constraints:

• $1 \leq$ words.length $\leq 1000$

• $1 \leq$ words[i].length $\leq 1000$

• All strings in words have the same length.

• $1 \leq$ target.length $\leq 1000$

• words[i] and target contain only lowercase English letters.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.