SPOJ.com - Problem LARSUBP

LARSUBP - Large subsequence Problem

#tree #binary-search

Given a string S which contains only digit-characters. How many subsequences can be obtained from S such that every digit is strictly greater than all previous digits in that subsequence.

As for example if S=7598 then there are 8 subsequences which follow the above constraint. These are 7, 5, 9, 8, 79, 78, 59, 58. Notice that 7598 is not a required subsequence because 7 > 5 and 9 > 8.

Note: A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Input

Input starts with an integer T (≤ 1000), denoting the number of test cases. Each case contains a string S. The length of S does not exceed 10000. S does not contain any leading zeros.

Output

For each case, print the a string(without quotes) "Case i: " followed by number of subsequences where "i" is test case number. Answer may be very large, so output it modulo 10^9+7.

Example

Input:

2
4
7598 Output: Case 1: 1
Case 2: 8

For small constraints: www.spoj.com/problems/SUBP/

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Being Human: 2014-08-11 14:40:10 Good one!! Not so tough..
	Flago: 2014-07-03 15:09:00 @green : 1 1233, ans=11
	ggkjh: 2014-07-01 22:16:05 what should be the o/p for 1 1233 is it 11 or 7..???
	Flago: 2014-06-26 09:27:32 Correcting a problem is fine, but maybe it should pop you an alert when one of your AC gets rejudged as not-AC.
	wisfaq: 2014-06-23 21:42:52 I think things are Ok now, no need to make an entirely new problem. Everybody can make a mistake. No bad feelings. I should have been warned by the fact that my Python solution unexpectedly got TLE for the original version. Now it gets AC :-) So blame me if you want. (except that the output description still doesn't match the wanted output; psetter could you please remove that # from the output description?) From Quantum--@wisfaq- It has beed updated. Thanx :) @Quantum: you're welcome. Last edit: 2014-06-23 21:50:06
	Rishav Goyal: 2014-06-23 21:42:52 yeah. totally agree with Francky.
	Francky: 2014-06-23 21:42:52 @psetter : There's yet some AC submissions. If you want to change things, and make most of those AC failed, then we prefer you to make another problem with good constraints, and limit. (The first edition could land in tutorial for example too). Thanks for your comprehension. From Quantum--@Francky----> I have updated the test files(fully tested) and statement too. So this is the new updated problem. And all submission are rejudged. Last edit: 2014-06-23 20:56:57
	P_Quantum: 2014-06-23 21:42:52 Due to some issues in test files, the problem has been modified little bit. The test files are updated and problem statement too. Sorry for the inconvenience. All the submissions will be rejudged shortly. @Louise- Thanks for pointing out the issue.
	louise: 2014-06-23 21:42:52 i m afraid that the answer cannot fit in unsigned-int64, since if the input is 10...01...12...2....9...9 (1000 times for each digit) then the output should be > 1000^10=10^30. BTW i try to solve it use BigInteger (hand written in C++) but got WA. so @author, could you please check the data for details?
	wisfaq: 2014-06-23 21:42:52 Thanks, Francky Last edit: 2014-06-22 14:03:12

Submit solution!

Added by:	P_Quantum
Date:	2014-06-21
Time limit:	1s-4s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64