BOJ - 14650 - 걷다보니 신천역 삼 (Small)

import sys

def solution():
    N = int(sys.stdin.readline())

    mod = 1000000009
    dp = [[0 for _ in range(3)] for _ in range(33334)]
    dp[2][0] = 0
    dp[2][1] = 1
    dp[2][2] = 1

    for i in range(3, (N+1)):
        for j in range(3):
            dp[i][j] = (dp[i - 1][j] % mod * 3) % mod

    print((dp[N][0] % mod + dp[N][1] % mod + dp[N][2] % mod) % mod)

solution()

https://www.acmicpc.net/problem/14650