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
Kartik Singal:
20120817 23:24:36
nice problem 

npsabari:
20120711 18:17:59
Classic! 

Symon Rahman:
20120517 21:15:38
Can anyone tell me what is the meaning of WA#1


Symon Rahman:
20120517 21:03:58
What is the test case 1, I got wa so many times, but my code is right 

Praneeth.N:
20120516 08:33:44
I am getting correct answer for the test cases mentioned in the question.But I am getting wrong answer #0.Somebody please kindly explain..Thanks in advance 

Giorgos Christoglou:
20120515 17:16:28
wrong answer at testcase 0 . 

Praneeth.N:
20120515 14:07:56
what does wrong answer #0 mean?? Thanks in advance. 

foreigner:
20120316 08:56:13
what does wrong answer#1 mean?? , 

Harshal Choudhary:
20120207 12:32:59
yea its written in the question itself "including empty subsequence" 

Buda IM (retired):
20110717 04:12:49
Can string be empty ?

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 