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


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

hide comments
2014-06-23 21:42:52 Gnirut Zet Wall
Corrected, AC.

Last edit: 2014-06-22 11:15:59
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.