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 翻译