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
Nadbor Drozd:
20140122 11:31:06
linear time and still time limit exceeded. Tried switching from python to java and c++, but couldn't get them even past compilation on with these ancient versions of the language. I give up 

Savan Popat:
20140108 14:49:35
anybody please explain for which case answer will be negative. 

Ankit Jain:
20140102 09:44:27
ok..so after reading the previous comments...googled a bit about modulus...modified the solution...got ac.....but still unable to understand as to which test case gives us a negative value of dp[] because of which all this trouble is occuring...thanks in advance to anybody willing to explain this weird bahviour... 

Rishabh Saxena:
20131217 23:58:11
for those getting Wrong Answer #1.....they should look into the fact that they can get negative answer!!


aqfaridi:
20140408 23:55:38
good problem. think dp .. Last edit: 20130531 11:04:48 

hitachi:
20130515 02:43:16
for those getting WA#1...problem is i think in the mod operation Last edit: 20130515 02:45:16 

:):
20130424 15:36:17
awesome problem 

codecracker:
20130401 23:18:55
mod(x)=x%m working fine...no need for increasing overhead 

(^@_^@):
20130401 22:29:51
Last edit: 20130512 19:34:08 

_maverick:
20130323 16:08:57
wow DP problems fill ma life a gud classic one...

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 