Multiples of three from 0, 1, and 2 (Large)

Ukje likes the syllable sam, which is how Korean reads the number 3. He tacks it onto the end of his sentences for fun, so he decided to spend the day playing with the number 3 as well.

Build $N$-digit multiples of 3 using only the three digits 0, 1, and 2. The number you build is a natural number, so it cannot start with 0. How many such numbers are there?

The first line contains $N$. (1 ≤ $N$ ≤ 33,333)

Print how many $N$-digit multiples of 3 can be written with only the digits 0, 1, and 2. The count can grow very large, so print it modulo 1,000,000,009 ($10^9+9$).