Problem A
Triforce

Link (the famous green-hatted hero from the Legend of Zelda series), was really bored after yet again having saved the day. As he was relaxing in the sun at Lake Hylia, he noticed he could make really nice patterns in the sand, and then walk around in them. One of these patterns he discovered was the n-degree triforce pattern.

Most are already familiar with the 1-degree triforce, which simply is three triangles joined together by their vertices. The 2-degree triforce is two 1-degree triforces joined together, where one of them is turned up-side down, and the $n$-degree triforce is $n$ 1-degree triforces joined together side by side in an up-down-up-down-fashion. Link makes a hole in the sand at each triangle corner, and he connects them by drawing lines along the edges of the triangles. Then he walks between the holes along the lines he has drawn. So much fun!

Figure 1: 1, 2, and 3-degree triforces

Link has drawn an $n$-degree triforce, and is wondering about the number of ways he could walk between the holes of the pattern along the lines, such that he visits every hole while never visiting the same hole twice, and returns to the same hole from which he began his walk. You are to make a program which calculates the number of such paths for an $n$-degree triforce.

Input

Input will consist of a single integer $1 \le n \le 10\, 000$ – the degree of the triforce.

Output

Output consists of a single integer – the number of paths Link can walk. Two paths are considered different if they don’t consist of exactly the same edges. This number may be large, so output it modulo $1\, 000\, 009$.

1

1

2

4