The Rabbit's Escape Route

A fox and a rabbit are on a $3 \times N$ grid. The rabbit starts at the top left cell and runs for the bottom right cell.

The fox chases the rabbit and drops a trap on every cell the rabbit has already crossed, so the rabbit can never step on the same cell twice. In one move the rabbit goes to a cell that shares a side with its current cell, that is, one step up, down, left, or right.

Count the routes the rabbit can take from the start cell to the goal cell. Two routes are different when the sequence of visited cells differs anywhere.

The first line contains the width $N$ of the grid. ($1 \le N \le 1000$)

Print the number of routes on the $3 \times N$ grid that go from the top left cell to the bottom right cell without visiting any cell twice, modulo $1000000009$ ($10^9 + 9$).