Hedwig's Ladder

Hedwig the hamster enjoys exploring networks of hamster tubes. Each day, Hedwig's owner rearranges the tubes to form a new network of tubes.

One day, Hedwig awoke to find that the network of tubes had been arranged in a ladder pattern as shown below, where each junction point (An and Bn) contained a small piece of carrot (Hedwig loves carrots!). Hedwig had not yet explored the new tube network and had no idea how long it was (it may go on forever!).

Hedwig decided to make a game. Given a length, the game asks how many paths of that length start from A0, using these rules: each time a junction is reached, Hedwig eats the piece of carrot there. A junction can only be used if a piece of carrot is still there when Hedwig arrives.

To help Hedwig, write a program that counts the paths from A0 of a specified length that do not hit any junction more than once. For example, all the paths of length 3 are shown below:

The first line of input contains a single decimal integer $P$ ($1 \le P \le 800$), the number of data sets that follow. Each data set is processed identically and independently.

Each data set is one line containing the data set number $K$, followed by the length $N$ ($1 \le N \le 1000$) of the paths to be counted.

For each data set, output one line containing the data set number $K$, followed by the number of paths of length $N$ modulo 10007.