14553번 - The Way

여우와 토끼는 사이가 좋았다. 하지만 어느 날 토끼가 여우에게 갓겜 "히어로즈 오브 더 스톰"을 추천했고, 여우는 게임을 해보고 너무 화가나서 토끼를 쫓으러 갔다.

히어로즈 오브 더 스톰의 맵을 단순화 시켜서 $3 \times N$격자라고 하고, 가장 왼쪽 위에서 토끼가 나왔다. 여우는, 토끼를 쫓아 가면서, 한번 왔던 격자에, 다시 돌아가지 못하도록 함정을 설치했다. 그래서 토끼는 칸을 중복해서 지나지 못한다. 토끼는 가장 오른쪽 아래 칸으로 안전을 보장받기 위해 가려고 한다.

이걸 보던 뉴쉐프는, 토끼가 도망칠 수 있는 가짓수가 궁금했다. 뉴쉐프의 궁금증을 풀어주자.

첫째 줄에, 격자의 가로 길이 $N$이 주어진다. ($1 \le N \le 1000$)

$3 \times N$ 격자를 칸을 중복해서 지나지 않고, 왼쪽 위에서 오른쪽 아래로 가는 경우의 수를 1000000009($10^9 + 9$)로 나눈 나머지를 구하라.