Background

Special for beginners, ^_^

Description

楼梯有 $N$ 级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递推程序，计算共有多少种不同走法？

Format

Input

一个整数 $N(1 \le N \le 40)$，为台阶的级数。

Output

一个整数，为不同走法数。

Samples

3

3

4

5

Limitation

1s, 1024KiB for each test case.