Description

Teacher Shu is climbing stairs. He can take either $1$ or $2$ steps at a time. Given the number of stairs, find the number of different ways to climb them.
For example: If there are $3$ stairs, he can take one step each time, or take one step first and then two steps, or take two steps first and then one step, for a total of $3$ different methods.

Input Format

The input contains several lines, each containing a positive integer $N$ representing the number of stairs, where $1≤N≤30$.

Output Format

The number of different ways to climb the stairs, with one output line for each input line.

Sample

5
8
10

8
34
89