题目描述

每次可以走 1、2 或 3 级台阶。给定 $n$，求恰好走到第 $n$ 级的方案数，答案对 $1000000007$ 取模。

输入格式

一行一个整数 $n$。

输出格式

输出方案数对 $1000000007$ 取模的结果。

样例

4

7

数据规模与约定

$0\le n\le10000000$。规定到达第 0 级有 1 种方案。