import sys
input = sys.stdin.readline
mod = 1000000007
D = int(input())
graph = [[0]*8 for i in range(8)]
graph[0][1] = graph[0][2] = 1
graph[1][0] = graph[1][2] = graph[1][3] = 1
graph[2][0] = graph[2][1] = graph[2][3] = graph[2][4] = 1
graph[3][1] = graph[3][2] = graph[3][4] = graph[3][5] = 1
graph[4][2] = graph[4][3] = graph[4][5] = graph[4][7] = 1
graph[5][3] = graph[5][4] = graph[5][6] = 1
graph[6][5] = graph[6][7] = 1
graph[7][4] = graph[7][6] = 1
DP = [[0]*(D+1) for i in range(8)]
DP[0][0] = 1
for i in range(1,D+1):
for now in range(8):
for last in range(8):
if graph[now][last]:
DP[now][i] += DP[last][i-1]%mod
print(DP[0][-1]%mod)
본대 산책 2의 풀이가 도저히 안떠올라서 본대 산책 1을 먼저 풀어보기로 했다.
난이도는 실버1로 매우 쉽다.
그냥 단순 DP이다.
오늘의 교훈) 본대 산책 2를 풀어보자