한 번에 계단을 1개 또는 2개 또는 3개를 뛰어오를 수 있는 사람이 있습니다.

바닥에서 시작하여 정수 n번째 계단까지 도달할 수 있는 방법의 총 가짓수를 구하는 프로그램을 작성하시오.

예를 들어,

• 1번째 계단에 도착하는 방법은 1가지 (1)
• 2번째 계단에 도착하는 방법은 2가지 (1+1, 2)
• 3번째 계단에 도착하는 방법은 4가지 (1+1+1, 1+2, 2+1, 3) 입니다.

입력

첫째 줄에 목적지 계단의 번호 n이 주어진다.

출력

바닥에서 n번째 계단까지 도착할 수 있는 방법의 가짓수를 첫째 줄에 출력한다.

제한 사항

• 1 ≤ n ≤ 25
• 결과값은 32비트 정수(int) 범위 내입니다.

금지 키워드

• for
• while
• goto

예제 입력 1

3

예제 출력 1

4

예제 입력 2

4

예제 출력 2

7