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

Updated:

```
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

## Leave a comment