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
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
Vikrant Singh: 2016-03-02 10:38:39

beauty !

PRANJIT BHARALI: 2016-02-04 22:22:33

be careful with MOD ...!!!

SM_92: 2015-12-25 13:08:34

Thanks to Shashank Tiwari for his comment , got ac after correcting mod problem.

Utkarsh Agarwal: 2015-12-08 02:07:01

Any python code accepted ?? mine is giving tle . same logic accepted in c++

rahul2907: 2015-09-26 14:05:23

do, if value of sum<0 then sum+=MOD
hope this will helps :)

7Bubble: 2015-09-01 12:31:43

This may be helpful.
input:
1
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
output:
84777677

kartikeya : 2015-07-13 14:56:37

stored strlen(s) in a different variable....and got ac after 10 tles!!!!!!
wasted my whole day!!!

Last edit: 2015-07-13 15:09:45

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: C++ 5
Resource:CodeCraft 08, Problem Setter: Jin Bin