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
aqfaridi: 2014-04-08 23:55:38

good problem. think dp ..

Last edit: 2013-05-31 11:04:48
hitachi: 2013-05-15 02:43:16

for those getting WA#1...problem is i think in the mod operation

Last edit: 2013-05-15 02:45:16
:-): 2013-04-24 15:36:17

awesome problem

codecracker: 2013-04-01 23:18:55

mod(x)=x%m working fine...no need for increasing overhead

(^@_^@): 2013-04-01 22:29:51

Last edit: 2013-05-12 19:34:08
_maverick: 2013-03-23 16:08:57

wow DP problems fill ma life a gud classic one...
and don't forget to mod costed me one WA ;)

Kartik Singal: 2012-08-17 23:24:36

nice problem

npsabari: 2012-07-11 18:17:59

Classic!

Symon Rahman: 2012-05-17 21:15:38

Can anyone tell me what is the meaning of WA#1

Symon Rahman: 2012-05-17 21:03:58

What is the test case 1, I got wa so many times, but my code is right


Added by:Ajay Somani
Date:2008-02-05
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