You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Fibonacci数列的递推公式为：$F_n = F_{n-1} + F_{n-2}$

已知： $F_1 = = F_2 = 1$

Format

Input

输入包含一个整数n。(1<=n<=10000000)

Output

输出一行，包含一个整数，表示$F_n$除以10007的余数。

Samples

10

55

hint

在本题中，答案是要求$F_n$除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出$F_n$的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

Limitation

1s, 1024KiB for each test case.