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:0.245s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: C++ 4.0.0-8
Resource:CodeCraft 08, Problem Setter: Jin Bin

hide comments
2014-12-17 15:56:17 rajat arora
great question to test knowledge abt modulus
2014-11-27 07:39:28 numerix
New time limit (set during switch to Cube cluster) is too strict for slower languages. My former Python AC solution (using psyco) cannot pass any more.
The problem is not a hard one, there are 1000+ AC users, so it shouldn't be a problem to increase the TL to allow slower languages to pass.
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.