Playing with Fire

Time limit1sMemory limit128 MB

Summary

Two distinct people start just above the burning top tile and each step down or diagonally, never landing on the same tile; count escape sequences.

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

Problem

Giwoong and Minsu like playing with fire in a corner of their lab. One day, while they were at it, the lab caught fire.

The lab floor is covered with square tiles of side length $1$ , and the room is a right triangle, as in the picture below. The top row holds $1$ tile, the row under it holds $2$ , and the $i$ -th row from the top holds $i$ tiles. There are $n$ rows in total. The two were playing with fire on the single tile of the top row, the sharp corner of the triangle.

The fire on that corner tile spreads one tile per second horizontally, vertically and diagonally. Giwoong and Minsu started running from the burning tile exactly $1$ second before it went up. In one second a person can move one tile, either straight down or diagonally down to the right. Except for the tile where they were playing with fire, if the two ever stand on the same tile they bump into each other, fall over, and get burned.

The walls that touch the corner have no door. Reaching the opposite wall, which is the bottom row, lets a person leave the lab through the door. Giwoong and Minsu are told apart from each other. Count the ways for both of them to escape the room safely.

Input

The first line contains $n$ , the length of one side of the room. ( $1 < n \le 100$ )

Output

On the first line, print the number of ways for both people to get out of the room safely, modulo $10007$ .

Hint

For $n = 3$ each person moves twice. The safe cases are the following $6$ .

Giwoong (down, down), Minsu (diagonal, down)
Giwoong (down, down), Minsu (diagonal, diagonal)
Giwoong (down, diagonal), Minsu (diagonal, diagonal)
Giwoong (diagonal, down), Minsu (down, down)
Giwoong (diagonal, diagonal), Minsu (down, down)
Giwoong (diagonal, diagonal), Minsu (down, diagonal)

Examples3

Example 1
Input
```
2
```
Expected output
```
2
```
Example 2
Input
```
3
```
Expected output
```
6
```
Example 3
Input
```
4
```
Expected output
```
20
```