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

Time limit2sMemory limit256 MB

Summary

Count N-digit numbers made only of the digits 0, 1, and 2 that are divisible by 3, with no leading zero, modulo 1e9+9.

Level: Medium4 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

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?

Input

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

Output

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$ ).

Examples3

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
3
```
Expected output
```
6
```
Example 3
Input
```
10
```
Expected output
```
13122
```