U637812 三波那契数列

有一种数列叫做“Tribonacci 数列”。这个数列的每一项等于它前三项的和。 具体地，定义如下： 1. $a_1 = 0$，$a_2 = 0$，$a_3 = 1$ 2. $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ 作为参考，下面给出 Tribonacci 数列的部分项： | 项数 | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ | $a_6$ | $a_7$ | $a_8$ | …… | $a_n$ | | :--- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :--------------------------------------- | | 值 | 0 | 0 | 1 | 1 | 2 | 4 | 7 | 13 | …… | $a_{n-1} + a_{n-2} + a_{n-3}$ | 由于答案可能很大，所以你只需要输出 $a_n$ 除以 $10^9 + 7$ 的余数即可。

输入包含一行，一个整数 $n$。

输出一行，表示 Tribonacci 数列的第 $n$ 项 $a_n$ 除以 $10^9 + 7$ 的余数。

#### 数据规模与约定 - 对于 $20\%$ 的数据，$n \le 10^6$ - 对于 $50\%$ 的数据，$n \le 10^9$ - 对于 $100\%$ 的数据，$1 \le n \le 10^{12}$