Background

小青蛙要跳到第 $n$ 块石头，它每次可以跳 $1$ 块、$2$ 块或者 $3$ 块。

Description

请用递归求出小青蛙跳到第 $n$ 块石头一共有多少种跳法。

想一想：最后一步可能从第 $n-1$、$n-2$ 或 $n-3$ 块石头跳过来。

Format

Input

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

Output

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

Samples

4

7

Hint

递归关系：$f(1)=1$，$f(2)=2$，$f(3)=4$，$f(n)=f(n-1)+f(n-2)+f(n-3)$。 这是兔子跳台阶的“三阶升级版”。

Limitation

1s, 256MiB for each test case.