불장난

기웅이와 민수는 랩실 구석에서 불장난을 하는 걸 좋아한다. 어느 날 두 사람이 불장난을 하던 중 랩실에 불이 났다.

랩실 바닥은 한 변의 길이가 $1$인 정사각형 타일로 덮여 있고, 방은 아래 그림처럼 직각삼각형 모양이다. 맨 윗줄에는 타일이 $1$개, 그 아래 줄에는 $2$개 있고, 위에서 $i$번째 줄에는 타일이 $i$개 있다. 줄은 모두 $n$개다. 두 사람은 맨 윗줄의 타일, 곧 삼각형의 뾰족한 구석에서 불장난을 하고 있었다.

구석 타일에 붙은 불은 매 초마다 가로, 세로, 대각선 방향으로 한 타일씩 번진다. 기웅이와 민수는 불이 타오르기 딱 $1$초 전에 그 타일에서 도망가기 시작했다. 두 사람은 $1$초에 바로 아래 또는 오른쪽 아래 대각선으로만 한 칸을 움직일 수 있다. 처음 불장난을 하던 타일을 빼고, 어느 순간이든 두 사람이 같은 타일 위에 서면 서로 부딪혀서 넘어지고 뜨거운 맛을 보게 된다.

불장난을 하던 구석과 접한 벽에는 문이 없다. 맞은편 벽, 곧 맨 아랫줄에 닿으면 문을 통해 랩실 밖으로 나갈 수 있다. 기웅이와 민수는 서로 구별한다. 두 사람이 모두 안전하게 방을 탈출하는 경우의 수를 구하자.

첫째 줄에 방의 한 모서리의 길이 $n$이 주어진다. ($1 < n \le 100$)

두 사람이 안전하게 방을 빠져나오는 경우의 수를 $10007$로 나눈 나머지를 첫째 줄에 출력한다.

$n = 3$이면 두 사람은 각각 두 번 움직인다. 안전한 경우는 다음 $6$가지다.

• 기웅 (아래, 아래), 민수 (대각, 아래)
• 기웅 (아래, 아래), 민수 (대각, 대각)
• 기웅 (아래, 대각), 민수 (대각, 대각)
• 기웅 (대각, 아래), 민수 (아래, 아래)
• 기웅 (대각, 대각), 민수 (아래, 아래)
• 기웅 (대각, 대각), 민수 (아래, 대각)