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
praval_singhal:
20160517 15:23:51
Misread Max String Length as 10,000. Got SegFault. AC in 2nd Attempt. :) 

Megreli:
20160512 12:47:02
I have o(n) solution in Java and getting TLE :\


top34051:
20160419 07:57:18
The best!! 

Archit Jain:
20160415 15:39:14
really nice DP 

lakshay_v06:
20160324 09:17:58
Woaaahhh! Gr8 Question. Done in O(n) :) .... Thanks to Shashank Tiwari for the tips! :D Last edit: 20160324 09:19:35 

Vikrant Singh:
20160302 10:38:39
beauty ! 

PRANJIT BHARALI:
20160204 22:22:33
be careful with MOD ...!!!


SM_92:
20151225 13:08:34
Thanks to Shashank Tiwari for his comment , got ac after correcting mod problem. 

Utkarsh Agarwal:
20151208 02:07:01
Any python code accepted ?? mine is giving tle . same logic accepted in c++ 

rahul2907:
20150926 14:05:23
do, if value of sum<0 then sum+=MOD

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 