문제

구름이는 주차 구역을 나누고 있다. 보통 주차 구역을 나눌 때는 한 가지 색상의 선을 그어서 영역을 구분하지만, 예술가인 구름이는 주차 구역을 여러 가지 색으로 색칠하는 방법으로 구역을 나누기로 한다.

주차장은 세로 길이가 , 가로 길이가  크기의 공간이다. 구름이는 이 공간을  크기의 구역 개로 나눈 뒤, 각 구역에 색을 칠해서 영역을 구분하고자 한다. 이 작업을 위해 구름이는 가지 색의 페인트를 각각 개씩 주문했고, 아래 규칙에 따라 각 구역을 칠할 것이다.

• 개의 페인트는  크기의 구역 하나를 색칠하는 데만 사용한다. 페인트의 양은 항상 해당 구역을 다 칠하기에 충분하다.
• 양옆으로 인접한 주차 구역은 서로 다른 색으로 칠한다.
• 같은 색으로 칠해진 두 구역은 같은 구역으로 나눠진 것으로 본다.
• 색의 배치가 다르더라도, 나눠진 주차 구역이 모두 동일하다면 같은 방식으로 나눠진 것으로 본다.

이때 주차 구역을 나눌 수 있는 모든 경우의 수를 구하시오. 단, 경우의 수가 너무 커질 수 있으니 이를 로 나눈 나머지를 출력한다.

예제 설명

주차장의 가로 길이가 6일 때, 주차 구역을 나누는 방법은 아래 5가지이다.

입력

첫째 줄에 정수 이 주어진다.

출력

주차 구역을 나눌 수 있는 모든 경우의 수를 로 나눈 나머지를 출력하시오.