289. Distinct Subsequences II (Modulo 10^9+7)

Given a string s, return the number of distinct non-empty subsequences of s, modulo 10^9+7. Subsequences yielding identical strings are counted once.

Input: A quoted string s.

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

Examples

Example 1

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

Example 2

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

Example 3

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