DSUBSEQ - Distinct Subsequences


Given a string, count the number of distinct subsequences of it (including empty subsequence). For the uninformed, a subsequence of a string is a new string which is formed from the original string by deleting some of the characters without disturbing the relative positions of the remaining characters.
For example, "AGH" is a subsequence of "ABCDEFGH" while "AHG" is not.

Input

First line of input contains an integer T which is equal to the number of test cases. You are required to process all test cases. Each of next T lines contains a string s.

Output

Output consists of T lines. Ith line in the output corresponds to the number of distinct subsequences of ith input string. Since, this number could be very large, you need to output ans%1000000007 where ans is the number of distinct subsequences.

Example

Input:
3
AAA
ABCDEFG
CODECRAFT

Output:
4
128
496

Constraints and Limits

T ≤ 100, length(S) ≤ 100000
All input strings shall contain only uppercase letters.


hide comments
atomic_lattice: 2023-10-06 13:18:38

Try doing with O(n) time and O(26) space

ive1010: 2022-03-22 18:24:57

Spoiler : make a 1d dp and try to find the # of subsequence ending at index 'i',
then take the sum for all 'i'
You must not look behind the repeated character.

pradeep_7: 2020-10-11 07:22:32

Approach :
Lets Take : "ABC"
o/p = 8;

va [0] = "" (1)
va[1]( untill A) = "" , A (2)
va[2]( untill B) = "" , A,B,AB (4)
va[3]( until C) = "",A,B,AB,C,BC,AC,ABC (8)
Pattern !

Hint: Duplicates ("ABB")
o/p is not 8
o/p is 6

manish_thakur: 2020-05-22 19:29:49

good problem , beware of mod of negative values

mrmajumder: 2020-04-21 13:13:22

Beware of negative values, if you're getting wa for modding

mrmajumder: 2020-04-21 13:13:06

Beware of negative values, if you're getting wa for modding

cpp219: 2020-01-29 04:17:21

good problem :)

hetp111: 2020-01-15 19:08:48

how do you do these kinds of dp problems by top down method ?

nyawriter: 2019-12-28 12:44:39

Negative value..

somz22: 2019-05-31 14:40:40

Try to do it in O(n), not O(26*n) it's possible just make dp relation properly.


Added by:Ajay Somani
Date:2008-02-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:CodeCraft 08, Problem Setter: Jin Bin