LARSUBP  Large subsequence Problem
Given a string S which contains only digitcharacters. 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: 8For small constraints: www.spoj.com/problems/SUBP/
hide comments
vineetjai:
20200918 20:05:37
dp of n*10 will work 

deadpool_18:
20171002 09:46:06
Please do not confuse others.. it is as mentioned in the problem, i.e. strictly greater.


viratian_070:
20170707 18:59:06
dp is everywhere....good question...AC in 0.13 

l0gic_b0mb:
20170606 20:01:47
My 100th :D 

omprakash_40:
20170412 12:09:55
AC in one go. used BIT tree .


omprakash_40:
20170412 12:08:18
Last edit: 20170412 12:10:30 

avisheksanvas:
20160817 11:50:20
Had come here following the tree tag! Went back with a different AC solution ;)


naruto09:
20160331 16:39:45
@priteshranjan:It is strictly greater only...i got AC assuming the problem statement is correct.. 

gullu_mishra:
20151031 07:30:13
dp ;) in 1 go 

priteshranjan:
20150522 18:14:22
@Flago @ggkjh : thanks guys, Your comments helped me get an AC

Added by:  P_Quantum 
Date:  20140621 
Time limit:  1s4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 