strips, all of the same length; positions on the strips are columns 0, 1, 2, …. Build the word goal under these rules:
- the letters of goal are taken one at a time, left to right;
- the next letter goal[i] may be taken from any strip strips[j] at any column k where strips[j][k] == goal[i];
- after that, column k and every column to its left become unusable on all strips, so the next letter must come from further right.
Several letters may come from the same strip. Count the ways to build goal; two ways differ if some letter uses a different strip or column. Return the answer modulo 10⁹ + 7.strips=["ab", "ba"], goal="ab" → 1
The a must come from column 0 (strip "ab") and the b from column 1 (strip "ab" again). One way.
strips=["aaa", "aaa"], goal="aa" → 12
There are three choices of two columns, (0, 1), (0, 2) and (1, 2), and each letter can come from either strip: 3 · 2 · 2 = 12.
strips=["xy"], goal="yx" → 0
strips=["ab", "ba"], goal="ab"
1
Run checks the first 3 tests in your browser. Submit checks all 127 tests on the server, hidden ones included.