Background

小兔子要跳到第 $n$ 级台阶，它每次可以跳 $1$ 级，也可以跳 $2$ 级。

Description

请用递归求出跳到第 $n$ 级台阶一共有多少种不同的跳法。

想一想：跳到第 $n$ 级，最后一步要么从第 $n-1$ 级跳 $1$ 步，要么从第 $n-2$ 级跳 $2$ 步。

Format

Input

一行一个整数 $n$（$1 \le n \le 40$）。

Output

一行一个整数，表示跳法的总数。

Samples

4

5

Hint

递归关系：$f(1)=1$，$f(2)=2$，$f(n)=f(n-1)+f(n-2)$。

Limitation

1s, 256MiB for each test case.