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⁹+7.

Example

Input:

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

Submit solution!

hide comments

< Previous 1 2 Next >

	slothsphereoj: 2024-03-06 04:20:06 [Input] 7 4 7598 1233 247645690 1928638235321893109321358 1928310236127 102345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 [Output] Case 1: 1 Case 2: 8 Case 3: 11 Case 4: 64 Case 5: 613 Case 6: 117 Case 7: 790406719
	vineetjai: 2020-09-18 20:05:37 dp of n*10 will work
	deadpool_18: 2017-10-02 09:46:06 Please do not confuse others.. it is as mentioned in the problem, i.e. strictly greater. Although we were supposed to solve this using trees, DP is easier to implement. :) AC in 0.03 seconds :).
	viratian_070: 2017-07-07 18:59:06 dp is everywhere....good question...AC in 0.13
	avisheksanvas: 2016-08-17 11:50:20 Had come here following the tree tag! Went back with a different AC solution ;) DP is indeed an all rounder :p
	naruto09: 2016-03-31 16:39:45 @priteshranjan:It is strictly greater only...i got AC assuming the problem statement is correct..
	priteshranjan: 2015-05-22 18:14:22 @Flago @ggkjh : thanks guys, Your comments helped me get an AC "strictly greater" is misleading. it should be "greater than or equal to". Correct me if i got it wrong. :)
	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..???

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