Distinct Subsequences

Return the number of ways to pick characters of s (keeping their order) that spell t. Different choices of positions count as different ways. Return the answer modulo 10**9 + 7.

For s = "rabbbit" and t = "rabbit" the answer is 3.

The starter code is a plain recursion. It is correct but too slow for long strings.

Examples

Example 1

Input:

num_distinct('rabbbit', 'rabbit')

Output:

3

Example 2

Input:

num_distinct('babgbag', 'bag')

Output:

5

Constraints

• 0 <= len(s) <= 2000
• 0 <= len(t) <= 500
• Lower-case letters.