Ball Painting

Time limit2sMemory limit512 MB

Summary

Count paint orders on a 2 by N grid where each new ball must touch an already painted ball, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

There are $2N$ white balls on a table, arranged in two rows to form a $2 \times N$ rectangle. Jon has a bucket full of black paint and wants to paint every ball black, one ball at a time, following these rules:

The first ball he paints can be any of the $2N$ balls.
Every ball painted afterward must be adjacent to some ball that is already black. Two balls are adjacent when they sit next to each other horizontally, vertically, or diagonally.

Count the number of different orders in which Jon can paint all $2N$ balls while obeying the rules.

Input

The input consists of several test cases. Each test case is a single line containing an integer $N$ ( $1 \le N \le 1000$ ). The input ends with a line containing $N = 0$ .

Output

For each test case, print on its own line the number of orders in which Jon can paint all $2N$ balls according to the rules. This number can be very large, so print it modulo 1,000,000,007.

Examples4

Example 1
Input
```
1
2
3
0
```
Expected output
```
2
24
480
```
Example 2
Input
```
4
0
```
Expected output
```
13440
```
Example 3
Input
```
5
0
```
Expected output
```
483840
```
Example 4
Input
```
1
1
1
0
```
Expected output
```
2
2
2
```