237. Count Distinct Subsequences (Modulo 10^9+7)

Given a string s, return the number of distinct non-empty subsequences of s, modulo 10^9+7. Two subsequences are different if formed by deleting different sets of indices but yielding different strings (identical resulting strings count once).

Input: A quoted string s.

Output: Integer — count mod 10^9+7.

Examples

Input: "abc"
Output: 7
Explanation: a,b,c,ab,ac,bc,abc.

Input: "aba"
Output: 6
Explanation: a,b,ab,ba,aa,aba.

Input: "aaa"
Output: 3
Explanation: a,aa,aaa.

Constraints

• 1<=s.length<=2000

Asked by