욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 욱제는 3을 가지고 놀아보기로 했삼.</p>

3개 숫자(0, 1, 2)만 가지고 N자리 3의 배수를 만들어 보삼. 만드는 배수는 자연수 이삼. 0으로 시작하는 수는 만들 수 없는 수 이삼. 3의 배수가 몇 개나 나올 수 있삼?

입력 형식

N을 입력 받으삼 (1 ≤ N ≤ 33,333)

출력 형식

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

예제 입력 1

1

예제 출력 1

0

예제 입력 2

3

예제 출력 2

6

예제 입력 3

10

예제 출력 3

13122