#J20001. 爬楼梯

爬楼梯

Background

Special for beginners, ^_^

Description

有n个台阶,小明一次可以爬1层,一次也可以爬2层,一次也可以爬3层,请问小明爬到第n层有多少种不同的爬法。例如,n=3的时候有4种不同的爬法,分别是1 1 1 ,1 2 , 2 1, 3 。

Format

Input

一个整数n表示小明要爬到第几个台阶

Output

输出一个整数 表示 爬到第n个台阶有多少种不同的爬法。

Samples

4
7

Limitation

1<=n<=50