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
somz22:
20190531 14:40:40
Try to do it in O(n), not O(26*n) it's possible just make dp relation properly. 

aj_254:
20190506 11:17:37
solvable in python play ez .not much optimization required just use dp and standard input output 

f00zz:
20190430 12:24:11
@deepak097 thanks for spoiling the problem :( 

deepak097:
20190328 06:37:58
Got AC :) complexity O(n*26) 

abhinav_jain02:
20190105 19:47:50
Very very Good DP Question with interesting optimization. It took a lot of time to crack this. 

horizon121:
20180517 12:52:39
Nice problem!!


chutuanthong:
20171220 11:32:09
dynamic programing easy 

kmkhan_014:
20171211 16:30:59
Last edit: 20190626 21:32:13 

javafreak:
20171028 23:37:16
Yes, it is important to add 'mod' wherever the answer can be negative. GeeksforGeeks tutorial might be helpful. 

raghav_chawla7:
20170925 09:27:12
take care of mod.Cost me 1WA 
Added by:  Ajay Somani 
Date:  20080205 
Time limit:  0.245s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  CodeCraft 08, Problem Setter: Jin Bin 