Description

有一座楼梯共有 n 级台阶。每一步可以选择向上走 1 级、2 级或 3 级台阶。问从第 0 级走到第 n 级，一共有多少种不同的走法。

Input

输入一个整数 n，表示台阶总数。

Output

输出一个整数，表示走到第 n 级台阶的不同方法总数。

Samples

input

3

output

4