← 返回题目列表

AtCoder · abc006_2

B. Tribonacci 序列

中文机器翻译题面 查看原题

問題文

有一个叫做 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 是 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 后的余数。