N개의 계단이 있습니다. 계단을 한 번에 1칸, 2칸, 또는 3칸을 오를 수 있습니다.

하지만 한번에 3칸을 오르고 나면 힘이 들어서, 이후 두 번의 이동 동안은 3칸을 오를 수 없고 오직 1칸 또는 2칸만 오를 수 있습니다.

(1칸이나 2칸은 아무런 제약 없이 언제든 오를 수 있습니다.)

계단의 수 N이 입력되면 주현이가 이 규칙을 지키며 n번째 계단에 정확히 도달할 수 있는 서로 다른 방법의 수를 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에 계단의 수 N이 입력된다.

출력

계단을 오를 수 있는 경우의 수를 첫째 줄에 출력한다.

제한 사항

• 1 ≤ N ≤ 15

예제 입력 1

4

예제 출력 1

7

예제 입력 2

6

예제 출력 2

23