헤드위그의 사다리

햄스터 헤드위그는 햄스터 튜브로 이루어진 네트워크를 탐험하는 것을 좋아한다. 매일 주인이 튜브를 다시 배열해서 새로운 튜브 네트워크를 만든다.

어느 날 헤드위그가 일어나 보니 튜브 네트워크가 아래 그림처럼 사다리 모양으로 배치되어 있었다. 각 교차점(An, Bn)에는 당근 조각이 하나씩 놓여 있다(헤드위그는 당근을 아주 좋아한다!). 헤드위그는 아직 새 튜브 네트워크를 탐험하지 않았고, 이 네트워크가 얼마나 긴지 알지 못한다(끝이 없을 수도 있다!).

헤드위그는 길이가 주어지면 시작점 A0에서 그 길이만큼 이동하는 경로가 몇 개인지 세는 게임을 만들었다. 규칙은 다음과 같다. 교차점에 도착할 때마다 헤드위그는 그곳의 당근을 먹는다. 교차점은 헤드위그가 도착했을 때 당근이 남아 있어야만 지날 수 있다.

헤드위그를 도와, A0에서 출발해 주어진 길이의 경로 중 어떤 교차점도 두 번 이상 지나지 않는 경로의 수를 구하는 프로그램을 작성하라. 예를 들어 길이 3인 경로는 모두 아래와 같다.

첫 줄에는 뒤따르는 데이터 세트의 개수를 나타내는 10진수 정수 $P$ ($1 \le P \le 800$)가 주어진다. 각 데이터 세트는 서로 독립적으로 같은 방식으로 처리된다.

각 데이터 세트는 한 줄로 이루어져 있으며, 데이터 세트 번호 $K$와 세야 할 경로의 길이 $N$ ($1 \le N \le 1000$)이 순서대로 주어진다.

각 데이터 세트에 대해 데이터 세트 번호 $K$에 이어, 길이 $N$인 경로의 수를 10007로 나눈 나머지를 한 줄에 출력한다.