같은 칸 수 연속 금지 계단

문제

운학은 0번째 칸에서 출발해 $N$번째 칸까지 계단을 오른다. 한 번에 1칸, 2칸, 3칸 가운데 하나를 오르는데, 바로 앞에서 오른 칸 수와 같은 칸 수로는 오르지 않는다. 예를 들어 1칸을 오른 다음에는 2칸이나 3칸만 오를 수 있다. 첫 번째 이동은 1칸, 2칸, 3칸 모두 할 수 있다.

$N$번째 칸을 넘어가면 안 되고, $N$번째 칸에 정확히 도착해야 한다. 오르는 순서가 다르면 다른 방법으로 센다. $N = 4$이면 1 → 2 → 1, 1 → 3, 3 → 1의 세 가지이다.

제한

• $1 \le N \le 40$

입출력 예시

입력 1

4

출력 1

3

입력 2

6

출력 2

8