20210223_코테공부

#12849 본대 산책 (실버1)

• 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.
• D 가 주어진다 (1 ≤ D ≤ 100,000) 
• 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.
• 참고

# 0 분에 어떤 지점에 도착할 수 있는 상태
# 0 : 정보과학과 1 : 전산관 2 : 미래관 3 : 신양관
# 4 : 한경직기념관 5 : 진리관 6 : 학생회관 7 : 형남공학관
DP = [1,0,0,0,0,0,0,0]

def nxt(state):
    tmp = [0 for _ in range(8)]
    tmp[0] = state[1] + state[2]
    tmp[1] = state[0] + state[2] + state[3]
    tmp[2] = state[0] + state[1] + state[3] + state[4]
    tmp[3] = state[1] + state[2] + state[4] + state[5]
    tmp[4] = state[2] + state[3] + state[5] + state[7]
    tmp[5] = state[3] + state[4] + state[6]
    tmp[6] = state[5] + state[7]
    tmp[7] = state[4] + state[6]
    return tmp

for i in range(int(input())):
    DP = nxt(DP)

print(DP[0]%1000000007)