Playing with Fire

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.

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

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

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)