SP20063 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 starts with an integer **T (, 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.**

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