Build target from left to right using characters from the equal-length strings in words. For each target character, choose a word and a matching character at some column. Chosen column indices must strictly increase, even when switching words. You may skip columns or reuse a word at later columns. Count all choices of word indices and columns that spell the target, modulo 1000000007. Identical words at different indices provide separate choices. Return 0 when no construction is possible.
Example 1:
Input: words = ["ab","ab"]
target = "ab"
Output: 4Explanation: Use column 0 for a and column 1 for b. Each column has two choices of word index, giving 2 times 2 = 4 constructions. Equal word contents still represent different choices.
Example 2:
Input: words = ["abc","abc"]
target = "ac"
Output: 4Explanation: Skip column 1. Either word supplies a at column 0, and either word supplies c at column 2, giving 4 constructions.
Example 3:
Input: words = ["ab","ba"]
target = "aaa"
Output: 0Explanation: Spelling three characters requires three distinct increasing column indices. The words have only two columns, so there are no valid constructions.
Constraints:
1 <= words.length <= 10001 <= words[i].length, target.length <= 1000- All words have the same length.
- All strings contain only lowercase English letters.