계단 오르기

첫 줄에 계단의 칸 수 n (1 이상 60 이하) 이 주어집니다.

한 번에 1칸, 2칸, 또는 3칸을 오를 수 있습니다. 맨 아래에서 n번째 칸까지 오르는 서로 다른 방법의 수를 출력하세요.

오르는 칸 수의 순서가 다르면 다른 방법입니다. 예를 들어 1 + 2 와 2 + 1 은 다릅니다.

예시

입력

3

출력

4