3954: AT_abc006_2 [ABC006B] 特里波那契数列
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：13
解决：5
题目描述
特里波那契数列定义如下：
a_1 = 0, a_2 = 0, a_3 = 1
a_n = a_{n-1} + a_{n-2} + a_{n-3}
数列前几项为：0, 0, 1, 1, 2, 4, 7, 13, ...
求该数列的第 n 项 a_n 除以 10007 的余数。
输入
输入从标准输入给出。
第 1 行给出整数 n (1 ≤ n ≤ 10^6)。
输出
输出特里波那契数列的第 n 项 a_n 除以 10007 的余数。
另外，输出的末尾需要加换行符。
样例输入 复制
7样例输出 复制
7