Distinct Subsequences

Write count_subsequences(text, word) that returns the number of ways to pick characters of text, at increasing positions, that spell out word. Two ways are different if they use a different set of positions in text.

An empty word can be picked in exactly one way: choose nothing.

Examples

count_subsequences("banana", "ban")  # returns 3
count_subsequences("aaaa", "aa")     # returns 6
count_subsequences("abc", "abcd")    # returns 0
count_subsequences("xyz", "")        # returns 1

In "banana" the b is at position 0, and the a and n can come from positions (1, 2), (1, 4) or (3, 4): three ways.

Constraints

• 0 <= len(text) <= 1000
• 0 <= len(word) <= 100
• Both strings contain lowercase letters only
• The answer can be very large