How many balanced ternary

A ternary representation is considered balanced if it has an equal number of even and odd digits (where $0$ is regarded as an even digit) and no prefix of the representation has more even digits than odd digits.

Given a number $N$ (0 < N \le 10^6), your task is to calculate the total number of balanced ternary representations of length $N$. The result should be presented modulo 1000000009 (10^9+9).