The whole world has become worried about the rapid spread of a virus. Scientists need to understand the folding of RNA of that virus so that they can have more information about its structure. The basic RNA-folding problem is defined by a string S of length n over the four-letter alphabet {A, U, C, G}, and an integer d (distance parameter). Each letter in this alphabet represents an RNA nucleotide. Nucleotides A and U are called complimentary as are the nucleotides C and G. A matching consists of a set M of disjoint pairs of positions of S, i.e. in a set M no position i can be paired with two different positions j and j′. If pair (i,j) is in M, then the nucleotide at i-th position is said to match the nucleotide at position j. A match is a permitted match if the nucleotides at sites i and j are complimentary, i < j and |i−j| > d. A matching M is non-crossing if and only if it does not contain any four sites i < i′ < j < j′ where (i,j) and (i′,j′) are matches in M. Finally, a permitted matching M is a matching that is non-crossing, where each match in M is a permitted match. The basic RNA-folding problem is to find a permitted matching of maximum cardinality. In this problem, you need to find the maximum cardinality of a permitted matching and the number of different sets M of that maximum cardinality. A set M is different from another set M′ if there exists at least one pair (i,j) in M and (i′,j′) in M′ such that either i and i′ or j and j′ are different. Input The first line of input file contains the number of test cases, T (1 ≤ T ≤ 80). Then T cases follow: Each case consists of two lines. The first line contains one integer: d (0 ≤ d ≤ |S|). Then the second line contains the string S (1 ≤ |S| ≤ 250). It will contain only the uppercase characters {A, U, C, G}. Output For each case, print ‘Case x: y z’ in a separate line, where x is the case number, y is the maximum cardinality and z is the number of sets with maximum cardinality. As the value of z can be very large, print z modulo 10007. Explanation of Sample cases: For 1st case, there is no pair of positions which satisfies the conditions of permitted match, i.e. empty set is the only possible answer. For 2nd case, the matches are shown below where the first position of a pair is denoted by ‘(’ and the other position is denoted by ‘)’: GGACCUUUUGGACGC ((.((....)).).) This is the only possible set with 4 permitted matches: {(1, 15), (2, 13), (4, 11), (5, 10)}. Sample Input 2 1 AUA 4 GGACCUUUUGGACGC
2/2 Sample Output Case 1: 0 1 Case 2: 4 1