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

1. $a_1 = 0$, $a_2 = 0$, $a_3 = 1$
2. $a_n = 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$ 行で出力してください。

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

7

7

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

1

0

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

100000

7927

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