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
Praneeth.N: 2012-05-16 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: 2012-05-15 17:16:28

wrong answer at testcase 0 .

Praneeth.N: 2012-05-15 14:07:56

what does wrong answer #0 mean?? Thanks in advance.

foreigner: 2012-03-16 08:56:13

what does wrong answer#1 mean?? ,

Harshal Choudhary: 2012-02-07 12:32:59

yea its written in the question itself "including empty subsequence"

Buda IM (retired): 2011-07-17 04:12:49

Can string be empty ?
It seems that it can ... I had to handle it to get AC

Last edit: 2011-04-28 22:52:12

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