Build a Target from Increasing Dictionary Columns

### Problem The strings in `words` have a common length. Build `target` from left to right by choosing a matching character from any word at a column strictly greater than the column used for the preceding target character. A word may supply more than one character at different permitted columns. Count the choices of word and column that form the target, modulo `10^9 + 7`. ```cpp class Solution { public: int numWays(vector<string>& words, string target); }; ``` ### Examples **Example 1:** ```text words = ["ab","ab"], target = "ab" Output: 4 Explanation: Either word can supply column 0 and independently either can supply column 1. ``` **Example 2:** ```text words = ["aaa"], target = "aa" Output: 3 Explanation: The chosen column pairs are (0,1), (0,2), and (1,2). ``` ### Constraints - `1 <= words.length <= 1000`. - All word lengths are equal and lie in `[1,1000]`. - `1 <= target.length <= 1000`. - Words and target use lowercase English letters only. ### Clarifying Questions Using a column makes that column and all earlier columns unavailable across every word, not just the chosen word. Equal strings at different list entries still offer distinct choices. ```hint Inspect the structure What makes two constructions distinct when equal strings appear at different word-list entries? ``` ### Reasoning checkpoints - Count choices by word occurrence and strictly increasing columns, retaining repeated-word multiplicity. - Show that no construction reuses a column or is counted more than once. ### Optional extensions Why must a one-dimensional target-prefix table be updated right-to-left?