Distinct Subsequence Pattern Matching

Statement

Given two strings, str1 and str2, return the number of times str2 appears in str1 as a subsequence.

Note: A string $X$ is a subsequence of string $Y$ if deleting some number of characters from $Y$ results in the string $X$.

Let’s assume that you have two strings as follows:

• str1 = "bbagbag"
• str2 = "bag"

In this example, str2 appears $7$ times in str1 as a subsequence:

1. bbagbag
2. bbagbag
3. bbagbag
4. bbagbag
5. bbagbag
6. bbagbag
7. bbagbag

Constraints:

• 1 $\leq$ str1.length, str2.length $\leq$ 500
• str1.length $\geq$ str2.length
• str1 and str2 consist of lowercase English letters

Examples