Fibonacci 数列

题目描述

$Fibonacci\,$数列的递推公式为：$F_n=F_{n-1}+F_{n-2}$，其中$\,F_1=F_2=1$。

当$\,n\,$比较大时，$F_n\,$也非常大，现在我们想知道，$F_n\,$除以$\,10007\,$的余数是多少。

输入格式

输入包含一个整数$\,n\,(1 \le n \le 10^6)$。

输出格式

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

样例输入 1

10

样例输出 1

55

样例输入 2

22

样例输出 2

7704

提示

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