782. Count Distinct Subsequences of a String (Modulo 10^9+7)

Given a string s, return the number of DISTINCT subsequences of s (including the empty subsequence), taken modulo 10^9 + 7. Two subsequences are distinct if their character-index selections differ. Duplicate-valued subsequences count only once. Implement with recursion + memoization or DP.

Input: A string s enclosed in double quotes.

Output: Return an integer count mod 10^9 + 7.

Examples

Input: "abc"
Output: 8
Explanation: Subsequences: '', a, b, c, ab, ac, bc, abc -> 8.

Input: "aab"
Output: 6
Explanation: '', a, b, aa, ab, aab -> 6 distinct.

Input: ""
Output: 1
Explanation: Only the empty subsequence.

Constraints

• 0 <= s.length <= 100

Asked by