N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair and there are exactly N chairs. So each person has exactly two neighboring chairs, one on the left and the other on the right. The host decides to shuffle the sitting arrangements. A person will be happy with the new arrangement if he can sit on his initial chair or on any of his initial neighboring chairs. Your job is to count number of different sitting arrangements such that at least K people are happy. Two arrangements are considered different, if there is at least one person sitting on a different chair in the arrangements. Input First line of the input contains T (1 ≤ T ≤ 50) which is the number of test cases. Each of the following T lines contain two space separated integers N (3 ≤ N ≤ 2000) and K (0 ≤ K ≤ N). Output Output the case number, followed by the number of different arrangements. Output the result modulo 1000000007. Note: For the 1st case, the 9 possible arrangements are {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 4, 1}, {4, 1, 2, 3}, {4, 2, 3, 1} and {4, 3, 2, 1}. Sample Input 3 44 42 500 250 Sample Output Case 1: 9 Case 2: 23 Case 3: 880811602