Finally, desperate Bilbo asked Gollum the following programming puzzle. Help the poor creature with his dinner! A = {A[1], A[2], . . . , A[N ]} is a sequence of lowercase letters. B = {B[1], B[2], . . . , B[K]} is another such sequence. B is called a subsequence of A if there exists a set of integers S = {S[1], S[2], . . . , S[K]} such that the following two conditions are true: (i) 1≤S[1]<S[2]<...<S[K]≤N (ii) A[S[i]]=B[i]forall1≤i≤K Here, S is called an occurrence of B in A. S is called the earliest occurrence of B in A, if there is no other occurrence Y such that, Y [j] < S[j] for some 1 ≤ j ≤ K. The earliest occurrence S of B in A is called a weak occurrence if, S[i+1]S[i] ≤ M for all 1 ≤ i < K. Here, M is called the weakness limit. Forexample,ifM=2then{b, c, d}hasaweakoccurrencein{a, b, y, c, d, c, d},but{a, c, d} doesn’t. You are given a forbidden sequence F of lowercase letters and a weakness limit M. A sequence X of length N is called strong if one of the following conditions is true: (i) the earliest occurrence of F in X is not a weak occurrence or (ii) F doesn’t occur in X at all. Write a program to calculate the number of strong sequences of lowercase letters of length N. Print the answer modulo 1000000007. Input The first line of the input contains T, the number of test cases. T ≤ 5000. Each test case consists of two lines. The first line contains a non-empty string of lowercase letters that denotes the forbidden sequence F which contains no more than 100 characters. The next line contains two positive integers M (1 ≤ M ≤ 10) and N (1 ≤ N ≤ 109), where M denotes the weakness limit and N denotes the desired length of the strong sequences. Output For each set of input, print the output in the format, ‘Case X: Y ’ where X is the serial of the input and Y is the desired output (see the sample output for clarification). Sample Input 2 ab 24 ww 12
2/2 Sample Output Case 1: 453750 Case 2: 675