問題文

トリボナッチ数列というものがあります。この数列は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$ で割った余りを出力することに気をつけてください。

---