問題文
有一个叫做 Tribonacci 数列的东西。这个数列是前三个数字之和。
严格来说,
被定义为。供参考,下面列出了 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 是 10007 求余数。
入力
n整数 n(1≦n≦10^6) 是 在 1 行中给出。
出力
Tribonacci 序列号 除以 n 項、a_n 是 10007 后的余数 请输出 1 行。
另外,在输出末尾放置一个换行符。 第入力例 1
7
出力例 1
7
- 7 个 tribonacci 数是 7 。
入力例 2
1
出力例 2
0
- 第一个 tribonacci 数是 请小心打印除以 0 。
入力例 3
100000
出力例 3
7927
- a_n 是 10007 后的余数。