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
m_alhussein_96: 2016-08-19 06:59:29

why I can't solve it top-down ?

Avik Sarkar: 2016-08-16 09:50:23

Be Careful With MOD .. The subtraction you are doing to remove the multiple occurrences may cause a negative result . That's why you have make it Positive .

singh1495: 2016-06-22 06:52:59

ACCEPTED in first go such a nice ques... takes time but nice dp

akshayvenkat: 2016-05-29 18:04:54

what is the maximum length of input string?

kshubham02: 2016-05-26 21:43:02

Thank you @PRANJIT BHARALI! Your comment saved me! I had totally forgotten about the MOD, got WA and was going mad testing different self-made test cases.
People...
"be careful with MOD ...!!!"

praval_singhal: 2016-05-17 15:23:51

Misread Max String Length as 10,000. Got SegFault. AC in 2nd Attempt. :)

Megreli: 2016-05-12 12:47:02

I have o(n) solution in Java and getting TLE :\

top34051: 2016-04-19 07:57:18

The best!!

Archit Jain: 2016-04-15 15:39:14

really nice DP

lakshay_v06: 2016-03-24 09:17:58

Woaaahhh! Gr8 Question. Done in O(n) :) .... Thanks to Shashank Tiwari for the tips! :D

Last edit: 2016-03-24 09:19:35

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