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
babur: 2017-06-29 09:01:15

One of the finest problem....loved to solve it :)

sandeep_4141: 2017-06-16 14:12:19

take care about MOD !!
cost me 1 WA !!

kabramanan: 2017-05-31 16:30:49

Just add mod wherever you think the answer could be negative.
Ex: ( (2*x - y) +m)%m
Few testcases:-
ABCABCABC=326
AABBAABBAA=139
MANANM=47
MISSISSIPPI=478

kush_code: 2017-05-17 18:20:38

input contains lowercase characters also.
cost me 3 WA

sfialok98: 2017-04-03 21:33:39

Very nice Problem.....
Just 8 lines of code...
Accepted in 1 Go...!!

nilabja16180: 2017-03-24 15:50:27

GOOD problem!

vunnamtej: 2017-03-09 14:51:24

good dp. string to maths

ipg_2015054: 2017-02-21 19:27:27

@Avik Sarkar how can the value be negative..please explain

prasoonbatham: 2017-01-14 15:17:38

Always check output before submitting. Cost me 1 wa. :(
Great question though!! Just observe the pattern :)

kira28: 2017-01-07 19:53:04

FINALLY AC :)
4 WAs due to MOD :/


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