Since you have been participating in programming contests and problem solving for quite a long time, I think most of you know about Alice and Bob :). They are responsible for inventing new games on various occasions. This time, they are back with a new game again. This new game is played in a one-dimensional board. The board contains N cells. The cells are numbered from 0 to N − 1, where the left most cell is marked as cell 0. Each cell can contain at most one piece. There are two kinds of pieces, gray and white. Alice moves all gray pieces, and bob moves all white ones. The pieces alternate, that is, leftmost piece is gray, next is white, next to that is gray, then it’s white again, and so on. There will always be equal number of black and gray pieces. At each move, the player selects at least one, and at most d of it’s pieces and move each one, either to it’s left or to it’s right, any number of cells (at least 1). Please note that, in each move, you can move some pieces left, and some pieces right, and also, you can keep some pieces unmoved, as long as, you move at least one of your pieces. But, it can neither jump over other pieces, nor it can move outside the board. The players alternate their moves. For example, if Alice decides to move the left most gray piece, these two moves are available to her. Moving the gray piece to the left Moving the gray piece to the right Alice moves first. The game ends, when someone is unable to make any move, and loses the game. You can assume that, both of them play optimally (that is, if it is possible to apply a strategy that will ensure someones win, they will always use that strategy). Although, in most occasions, they want to know, given the state of the game, who will win that game. But you are not required to find that here. Instead, Alice and Bob wrote a computer program to assist them in playing this game. The program generates the positions of all pieces randomly (the program always generate valid positions, that is no two piece are on the same cell, and the colors of the pieces alternate). You are asked that, given the size of the board, and the number of gray and white pieces, how many different configurations ensure that Alice will win? Input First line of input contains an integer T (≤ 100) the number of test cases. Each of the next T lines contain three integers, N (1 ≤ N ≤ 10000), K (1 ≤ K ≤ 100, K ≤ N) and d (1 ≤ d ≤ K), where N is the size of the board, and K is the number of pieces, and d is the maximum number of piece to move. K will always be an even number. Output For each test case, output the number configurations, where Alice wins. The result can be very large. So, output the number modulo 1000000007.
2/2 Sample Input 5 10 2 1 10 4 2 50 6 3 3642 68 10 5698 32 1 Sample Output 36 182 15874485 367653436 998833190