# Distinct Subsequences

Moderate
0/80
Average time to solve is 10m
Contributed by

## Problem statement

You have been given string 'S' of length 'N' that may contain duplicate alphabets. Your task is to return the count of distinct subsequences of it.

For example:

``````For the given string “deed” :
The possible subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“d”}, {“dd”}, {“ed”}, {“ded”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}.

As, {“d”}, {“e”}, {“de”}, {“ed”} and {“ded”} are repeated.

The distinct subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“dd”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}

Thus, the output will be 11.
``````

Note:

``````As the answer can be large, return your answer modulo 10^9  + 7.
``````
Detailed explanation ( Input/output format, Notes, Images )
Input format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case or query contains the string 'S'.
``````
Output format:
``````For each test case, print a single line containing the count of distinct subsequences modulo 10^9+7.

The output of each test case will be printed in a separate line.
``````

Note:

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
Constraints:
``````1 <= T <= 10
1 <= N <= 10 ^ 4

where 'T' is the number of test cases and 'N' is the length of the given string 'S'.

Time limit: 1 sec.
``````
##### Sample input 1:
``````2
abcd
``````
##### Sample output 1:
``````16
7
``````
##### Explanation
``````For test case 1:

Distinct subsequence are: {“”}, {a}, {b}, {ab}, {c}, {ac}, {bc}, {abc}, {d}, {ad}, {bd}, {abd}, {cd}, {acd}, {bcd} and {abcd}. Thus, the answer will be 16.

For test case 2:

For better understanding, let us take all the subsequences of string dad. They will be:

``````2
``````128