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
prasoonbatham:
20170114 15:17:38
Always check output before submitting. Cost me 1 wa. :(


kira28:
20170107 19:53:04
FINALLY AC :)


madhavgaba:
20161230 12:31:23
@VINAYAK if ur answer is negative.....just add MOD to ur answer 

vinayak_1997:
20161229 14:05:45
Why will modulo here give negative answer? Last edit: 20161229 14:31:38 

m_alhussein_96:
20160819 06:59:29
why I can't solve it topdown ? 

Avik Sarkar:
20160816 09:50:23
Be Careful With MOD .. The subtraction you are doing to remove the multiple occurrences may cause a negative result . That's why you have make it Positive . 

singh1495:
20160622 06:52:59
ACCEPTED in first go such a nice ques... takes time but nice dp 

akshayvenkat:
20160529 18:04:54
what is the maximum length of input string? 

kshubham02:
20160526 21:43:02
Thank you @PRANJIT BHARALI! Your comment saved me! I had totally forgotten about the MOD, got WA and was going mad testing different selfmade test cases.


praval_singhal:
20160517 15:23:51
Misread Max String Length as 10,000. Got SegFault. AC in 2nd Attempt. :) 
Added by:  Ajay Somani 
Date:  20080205 
Time limit:  0.245s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C++ 5 
Resource:  CodeCraft 08, Problem Setter: Jin Bin 