계단 오르기

계단이 N개 있습니다. 한 번에 1칸 또는 2칸씩 오를 수 있을 때, N번째 계단까지 오르는 방법의 수를 구하세요.

예를 들어 계단이 3개이면:

• 1+1+1
• 1+2
• 2+1

총 3가지 방법이 있습니다.

입력

첫째 줄에 계단의 수 N이 주어집니다.

출력

N번째 계단까지 오르는 방법의 수를 출력합니다.

제한 조건

• 1 ≤ N ≤ 45

예제

3

3

5

8

1

1