0, 1, 2로 만드는 3의 배수 (Large)

욱제는 '삼'이라는 음절을 참 좋아한삼. 인삼, 홍삼, 해삼, 삼식이, 삼시세끼, 알았삼, 그리고 특히 일이삼을 좋아한삼. 그래서 숫자 3을 가지고 놀아 보기로 했삼.

0, 1, 2 세 숫자만 써서 $N$자리 3의 배수를 만들어 보삼. 만드는 수는 자연수라서 0으로 시작할 수 없삼. 이런 수가 몇 개나 나올 수 있삼?

첫째 줄에 $N$이 주어진삼. (1 ≤ $N$ ≤ 33,333)

0, 1, 2만 써서 만들 수 있는 $N$자리 3의 배수의 개수를 출력하삼. 개수가 너무 커질 수 있으니 1,000,000,009 ($10^9+9$)로 나눈 나머지를 출력하삼.