B - トリボナッチ数列 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

トリボナッチ数列というものがあります。この数列は3つ前までの数字を足したものです。
厳密には、

  1. a_1 = 0, a_2 = 0, a_3 = 1
  2. a_n = a_{n-1} + a_{n-2} + a_{n-3}
と定義されています。参考までに、トリボナッチ数列表を掲載します。

# 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 行で与えられる。

出力

トリボナッチ数列の第 n 項、a_n を 10007 で割った余りを 1 行で出力してください。

また、出力の末尾には改行を入れること。

入力例 1

7

出力例 1

7
  • 7 番目のトリボナッチ数は 7 です。

入力例 2

1

出力例 2

0
  • 最初のトリボナッチ数は 0 です。

入力例 3

100000

出力例 3

7927
  • a_n を 10007 で割った余りを出力することに気をつけてください。