1층에서 2층으로 올라가는 계단을 생각해 보자 여러분은 계단을 어떻게 올라가는가? 안전하게 한 칸, 한 칸씩 오르는가? 

아니면 성큼성큼 두 칸씩 오르는가? 아니면 한 칸 또는 두 칸 마음 내키는 대로...? 

아마도 수많은 방법이 있을 것이다.

초등학생인 정진이는 아직 다리가 짧아 한 걸음에 계단을 최대 3개까지 오를 수 있다.

정진이가 n개의 계단을 오르는 모든 방법의 수를 계산하는 프로그램을 작성하시오.

예를 들어 2개의 계단으로 구성되어 있다면,

① 한 칸, 한 칸

② 두 칸

위와 같이 두 가지 방법이 존재하고,

예를 들어 3개의 계단으로 구성되어 있다면,

① 한 칸, 한 칸, 한 칸

② 한 칸, 두 칸

③ 두 칸, 한 칸

④ 세 칸

위와 같이 네 가지 방법이 존재한다.

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

(1 ≤ N ≤ 36)

첫 번째 줄에 계단을 오르는 방법의 수를 자연수로 출력한다.