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