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

여기서 10**9 + 9*1000000009이 아니라 그냥 1000000009입니다 이거 고치고 AC받았습니다.