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
7Bubble:
20150901 12:31:43
This may be helpful.


kartikeya :
20150713 14:56:37
stored strlen(s) in a different variable....and got ac after 10 tles!!!!!!


Shashank Tiwari:
20150701 11:40:23
If getting wrong answers , make sure of following points :


xxbloodysantaxx:
20150701 08:52:38
Dynamic programming :) is beautiful! 

ISHANI:
20150225 15:07:02
not so simple as i thought.. 

Swapnil Borse:
20141229 14:24:06
was fun solving this problem :) 

rajat arora:
20141217 15:56:17
great question to test knowledge abt modulus 

numerix:
20141127 07:39:28
New time limit (set during switch to Cube cluster) is too strict for slower languages. My former Python AC solution (using psyco) cannot pass any more.


tranquil:
20140523 17:01:45
getting WA#1 :(


P_Quantum:
20140523 10:36:06
Finally AC...don't use long long. 
Added by:  Ajay Somani 
Date:  20080205 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  CodeCraft 08, Problem Setter: Jin Bin 