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
2019-05-06 11:17:37
solvable in python play ez .not much optimization required just use dp and standard input output
2019-04-30 12:24:11
@deepak097 thanks for spoiling the problem :(
2019-03-28 06:37:58
Got AC :) complexity- O(n*26)
2019-01-05 19:47:50
Very very Good DP Question with interesting optimization. It took a lot of time to crack this.
2018-05-17 12:52:39
Nice problem!!
2017-12-20 11:32:09
dynamic programing easy
2017-10-28 23:37:16
Yes, it is important to add 'mod' wherever the answer can be negative. GeeksforGeeks tutorial might be helpful.
2017-09-25 09:27:12
take care of mod.Cost me 1WA
2017-06-29 09:01:15
One of the finest problem....loved to solve it :)
2017-06-16 14:12:19
take care about MOD !!
cost me 1 WA !!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.