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.


Added by:Ajay Somani
Date:2008-02-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:CodeCraft 08, Problem Setter: Jin Bin

hide comments
2016-03-02 10:38:39 Vikrant Singh
beauty !
2016-02-04 22:22:33 PRANJIT BHARALI
be careful with MOD ...!!!
2015-12-25 13:08:34 SM_92
Thanks to Shashank Tiwari for his comment , got ac after correcting mod problem.
2015-12-08 02:07:01 Utkarsh Agarwal
Any python code accepted ?? mine is giving tle . same logic accepted in c++
2015-09-26 14:05:23 rahul2907
do, if value of sum<0 then sum+=MOD
hope this will helps :)
2015-09-01 12:31:43 7Bubble
This may be helpful.
input:
1
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
output:
84777677
2015-07-13 14:56:37 kartikeya
stored strlen(s) in a different variable....and got ac after 10 tles!!!!!!
wasted my whole day!!!

Last edit: 2015-07-13 15:09:45
2015-07-01 11:40:23 Shashank Tiwari
If getting wrong answers , make sure of following points :

1. |S|>0 in all test cases , so relax.
2. mod 1000000007 can give 0. And if you subtract something from it then remainder can get negative.So ,
use this : (1000000007 +any_remainder)%1000000007 will always give answer between 0 and 1000000006.
Note: any_remainder can be negative.

3. If answer stored as integer check if addition gives integer overflow.
Make sure mod 1000000007 can give remainder upto 1000000006. Best is to use long long and not unsigned long long (for c++ users )

4. wrong answer on test case 0 shows wrong logic used :
check them :

5
A
AA
ABA
ABB
ABBAAABABABABABBABABABABABA

output :
2
3
7
6
514955
Hope that helps :)

Last edit: 2015-07-01 11:42:14
2015-07-01 08:52:38 xxbloodysantaxx
Dynamic programming :) is beautiful!
2015-02-25 15:07:02 ISHANI
not so simple as i thought..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.