题目描述：

トリボナッチ数列读作"斐力波那契数列"，数列中每一项是前三项的和

• $a_0=0,a_1=0,a_2=1$
• $a_{n}=a_{n-1}+a_{n-2}+a_{n-3}$

请求出数列的第n项

输入格式：

一个整数n

$1≤n≤10^6$

输出格式：

一个整数表示答案，结果可能很大，输出其对10007取余的结果

样例：

7

7

100000

7927

提示