Distinct Subsequences of a String

Given a string S of length N that may contain duplicate alphabets, your task is to compute the count of distinct subsequences of this string.

Example:

Input:

S = "deed"

Output:

11

Explanation:

The possible subsequences include: {""}, {"d"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"dd"}, {"ed"}, {"ded"}, {"eed"}, {"deed"}. Removing duplicates gives us 11 distinct subsequences.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^4

Note: The answer can be large, so return it modulo 10^9 + 7.

Input:

T (number of test cases)
string S (for each test case)

Output:

The count of distinct subsequences for each test case, displayed on separate lines.

Note: You do not need to print anything explicitly. Just implement the function to return the result.