공 색칠하기

탁자 위에 흰 공 $2N$개가 두 줄로 놓여 $2 \times N$ 직사각형을 이루고 있다. Jon은 검은 페인트가 가득 담긴 통을 가지고 있으며, 모든 공을 한 번에 하나씩 검게 칠하려고 한다. 칠하는 규칙은 다음과 같다.

• 가장 먼저 칠하는 공은 $2N$개 중 어느 것이든 될 수 있다.
• 그 다음부터 칠하는 공은 이미 검게 칠해진 어떤 공과 반드시 인접해야 한다. 두 공은 가로, 세로, 또는 대각선 방향으로 바로 옆에 있을 때 인접한 것으로 본다.

규칙을 지키면서 $2N$개의 공을 모두 칠하는 서로 다른 순서의 가짓수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $N$ ($1 \le N \le 1000$)이 적힌 한 줄로 주어진다. 입력의 마지막 줄에는 $N = 0$이 주어지며, 이 줄에서 입력이 끝난다.

각 테스트 케이스마다, 규칙에 따라 $2N$개의 공을 모두 칠하는 순서의 가짓수를 한 줄에 출력한다. 이 수는 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.