该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：stairs.in 输出文件：stairs.out

小明要爬 $N$ 级台阶。每次可以跳 $1$ 级、$2$ 级 或 $3$ 级，但不能连续两次跳相同的级数。

问：恰好爬到第 $N$ 级台阶的跳法一共有多少种？答案对 $10^9+7$ 取模。

输入格式

一行一个整数 $N$。

输出格式

输出方案总数，末尾换行。

样例

样例 1

2

1

样例说明：

只能一次跳 $2$ 级。

$1+1$ 因为连续跳两次 $1$ 级，不合法。

样例 2

4

3

样例说明：

合法方案：$(1,2,1)$、$(3,1)$、$(1,3)$。

样例 3

49993

407466683

数据范围

对于 20% 的数据，$N \le 10$。

对于 40% 的数据，$N \le 100$。

对于 60% 的数据，$N \le 1000$。

对于 80% 的数据，$N \le 10000$。

对于 100% 的数据，$1 \le N \le 10^6$。