A word search puzzle hides the word word inside the letter strip text: pick letters of text from left to right (not necessarily adjacent) that spell word. Two hidings are different if they use a different set of positions. Return the number of hidings modulo 10**9 + 7.
Examples
Input: text = "bananas", word = "ban"
Output: 3
Explanation: the "b" is fixed; (a, n) can use positions (1, 2), (1, 4) or (3, 4).
Input: text = "ab", word = "abc"
Output: 0
Constraints
0 <= len(text) <= 1000,1 <= len(word) <= 200- lowercase letters only
- Target complexity: O(len(text) * len(word)). The count itself can be astronomically large.
Goals
- Count, rather than detect, the ways one string sits inside another
- Compress a 2D table to one row by iterating in the right direction