Climbing Stairs

Problem Background

Special for beginners, ^_^

Problem Description

A staircase has $N$ steps. You can go up one step at a time, or two steps at a time. Write a recursive program to count the number of different ways to climb the stairs.

Input Format

One integer $N (1 \le N \le 40)$, the number of steps.

Output Format

One integer, the number of different ways.

Sample Input 1

3

Sample Output 1

3

Sample Input 2

4

Sample Output 2

5

Constraints

1 second, 1024 KiB for each test case.