LARSUBP - Large subsequence Problem


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: " follwed 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/


hide comments
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

l0gic_b0mb: 2017-06-06 20:01:47

My 100th :D

omprakash_40: 2017-04-12 12:09:55

AC in one go. used BIT tree .
nice problem.

omprakash_40: 2017-04-12 12:08:18

Last edit: 2017-04-12 12:10:30
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..

gullu_mishra: 2015-10-31 07:30:13

dp ;-) in 1 go

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


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