N = int(input())
hanoi = [0]
for i in range(N-1):
hanoi.append((hanoi[-1]*2+1)%1000000007)
print((3+hanoi[-1]*8)%1000000007)DP로 해결하였다.
일반 하노이탑과의 차이점을 생각하면 쉽게 해결할 수 있다.
가장 큰 블록을 순서대로 옮기기 위해서는 3번의 움직임이 필요하다. 이때 가장 큰 블록을 옮길 때마다 일반 하노이탑을 옮기듯이 나머지 하노이탑을 옮겨야하고, 가장 큰 블록을 다 옮기고 나서 나머지 하노이탑을 옮겨야 하므로 가장 큰 블록을 제외한 나머지 블록은 총 4번 옮긴다.
이때 4번 옮기면 짝수번 옮기는 셈이므로 순서는 변하지 않아 따로 조정할 필요가 없다. 모든 블록이 2개씩 있으므로, 가장 큰 블록을 제외한 나머지 블록을 옮기는 횟수는 일반 하노이탑을 옮기는 횟수*4*2번이다. 즉, "일반 하노이탑 N-1개를 옮기는 횟수*8+3"이 곧 정답이다.
이때 일반 하노이탑을 옮기는 횟수는 DP로 구할 수 있지만, 그냥 일반항을 구할 수도 있다.
일반 하노이탑의 일반항은 2^N-1 이다. 이를 이용하면, 색깔 하노이탑의 일반항도 구할 수 있다.
3+(2^(N-1)*8) = 2**(N+2)+5
따라서 아래와 같은 코드로도 통과할 수 있다.
print((2**(int(input())+2)-5)%1000000007)