Consider a sequence of n integers < 1 2 3 4 . . . n >. Since all the values are distinct, we know that there are n factorial permutations. A permutation is called K-transformed if the absolute difference between the original position and the new position of every element is at most K. Given n and K, you have to find out the total number of K-transformed permutations. Example: n=4,K=2 1 2 3 4 Valid Annotation (position) P1 1234 P2 1243 P3 1324 P4 1342 P5 1423 P6 1432 P7 2134 P8 2143 P9 2314 P10 2341 P11 2413 P12 2431 P13 3124 P14 3142 P15 3214 P16 3241 P17 3412 P18 3421 P19 4123 P20 4132 P21 4213 P22 4231 P23 4312 P24 4321 So, for the Input Yes The original sequence. All the elements are in their original position Yes 3 and 4 are reordered, but each is shifted by 1 position only. Yes Yes 2 is shifted by 2 positions. 2 ≤ K, so it’s a valid one. Yes Yes Yes Yes Yes No 1 is shifted by 3 positions. 3 > K and so this is an invalid permutation Yes No Yes Yes Yes No Yes No No 4 is shifted by 3 positions. 3 > K and so this is also invalid No No No No No Here, both 4 and 1 are breaking the property. above case, there are 14 2-transformed permutations. The first line of input is an integer T (T < 20) that indicates the number of test cases. Each case consists of a line containing two integers n and K. (1 ≤ n ≤ 109) and (0 ≤ K ≤ 3). Output For each case, output the case number first followed by the required result. Since the result could be huge, output result modulo 73405.
2/2 Sample Input 3 42 100 0 10 1 Sample Output Case 1: 14 Case 2: 1 Case 3: 89