SP19954 KN2 - Travelling Knight 2

Your task is simple. A knight is placed on the top left corner of a chessboard having **2_n_** rows and **2_n_** columns. In how many ways can it move such that it ends up at a corner after atmost **_k_** moves ? 

The first line contains an integer **_T_**, the number of test cases. Each of the next **_T_** lines contains 2 integers : **_n, k_**.

Output **_T_** lines, one for each test case, containing the required total number of configurations. Since the answer can get very big, output it modulo 1000007.