Sphere Online Judge

SPOJ Problem Set (classical)

2416. Distinct Subsequences

Problem code: DSUBSEQ


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:2s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: C++ 4.0.0-8
Resource:CodeCraft 08, Problem Setter: Jin Bin

hide comments
2014-05-23 17:01:45 tranquil
getting WA#1 :(
donno what is wrong....mod looks fine to me
2014-05-23 10:36:06 P_Quantum
Finally AC...don't use long long.
2014-01-22 11:31:06 Nadbor Drozd
linear time and still time limit exceeded. Tried switching from python to java and c++, but couldn't get them even past compilation on with these ancient versions of the language. I give up
2014-01-08 14:49:35 Savan Popat
anybody please explain for which case answer will be negative.
2014-01-02 09:44:27 Ankit Jain
ok..so after reading the previous comments...googled a bit about modulus...modified the solution...got ac.....but still unable to understand as to which test case gives us a negative value of dp[] because of which all this trouble is occuring...thanks in advance to anybody willing to explain this weird bahviour...
2013-12-17 23:58:11 Rishabh Saxena
for those getting Wrong Answer #1.....they should look into the fact that they can get negative answer!!
I just made some changes in my mod function to make it positive and it got accepted... :)
2014-04-08 23:55:38 αqfαяι∂ι™
good problem. think dp ..

Last edit: 2013-05-31 11:04:48
2013-05-15 02:43:16 hitachi
for those getting WA#1...problem is i think in the mod operation

Last edit: 2013-05-15 02:45:16
2013-04-24 15:36:17 :-)
awesome problem
2013-04-01 23:18:55 codecracker
mod(x)=x%m working fine...no need for increasing overhead
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.