问题描述

有一个叫做 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)$。

输出

将 Tribonacci 数列的第 $n$ 项 $a_n$ 对 $10007$ 求余数，并在一行中输出。

在输出末尾添加换行符。

---

输入例子 1

7

输出例子 1

7

• 第 $7$ 个 Tribonacci 数是 $7$。

---

输入例子 2

1

输出例子 2

0

• 第一个 Tribonacci 数是 $0$。

---

输入例子 3

100000

输出例子 3

7927

• 请注意输出 Tribonacci 数对 $10007$ 求余数。