문제

구름이는 수직선 모양의 칸으로 이루어진 주차장의 바닥을 빨강, 초록, 파란색으로 색칠하고 있습니다. 예술적 감각이 뛰어난 구름이는 주차장의 어떤 칸이 인접한 칸과 색이 다르기를 원합니다.

주차장의 첫째 칸은 어떤 색상이든 들어올 수 있다고 할 때, 구름이가 주차장을 색칠할 수 있는 경우의 수를 출력하세요.

입력

첫째 줄에 주차장의 크기 이 주어진다.

출력

구름이가 주차장을 칠하는 경우의 수를 로 나눈 나머지를 출력하시오.