AT_abc006_2.[ABC006B] トリボナッチ数列

有一种数列叫做“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}$

请你求出该数列的第 $n$ 项 $a_n$，并输出 $a_n$ 除以 $10007$ 的余数。

输入通过标准输入给出，格式如下：

$n$

其中，整数 $n$ 满足 $1 \leq n \leq 10^6$。请输出 Tribonacci 数列的第 $n$ 项 $a_n$ 除以 $10007$ 的余数，输出占一行。

另外，输出末尾需要换行。

例如：

7

7

• 第 7 项的 Tribonacci 数是 7。

1

0

• 第 1 项的 Tribonacci 数是 0。

100000

7927

• 注意输出 $a_n$ 除以 $10007$ 的余数。

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

输出一行，表示第 $n$ 项 Tribonacci 数列 $a_n$ 除以 $10007$ 的余数。

无。

由 ChatGPT 4.1 翻译