Distinct Subsequences Problem Statement

You are given a string 'S' of length 'N' which may include duplicate alphabets. Your goal is to calculate the number of distinct subsequences in the string.

Example:

Input:

"S" = "deed"

Output:

11

Explanation:

The possible subsequences are {""}, {"d"}, {"e"}, {"de"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"d"}, {"dd"}, {"ed"}, {"ded"}, {"ed"}, {"ded"}, {"eed"} and {"deed"}. After filtering duplicates, the distinct subsequences are: {""}, {"d"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"dd"}, {"ed"}, {"ded"}, {"eed"}, {"deed"}, resulting in 11 distinct subsequences.

Input:

The first line contains an integer 'T' denoting the number of test cases. Each of the following T lines contains a single string 'S'.

Output:

For each test case, output the count of distinct subsequences, modulo 109 + 7, on a new line.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 104

Note: The answer might be large, so return it modulo 10⁹ + 7.