3343：[中级组] Fibonacci 斐波那契数列
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：14
解决：3
题目描述
## 题目描述
Fibonacci 数列的递推公式为：$F_n=F_{n-1}+F_{n-2}$，其中 $F_1=F_2=1$。
当 $n$ 比较大时，$F_n$ 也非常大，现在我们想知道，$F_n$ 除以 $10007$ 的余数是多少。
## 输入格式
输入包含一个整数 $n$。
## 输出格式
输出一行，包含一个整数，表示 $F_n$ 除以 $10007$ 的余数。
## 样例
```input1
10
```
```output1
55
```
```input2
22
```
```output2
7704
```
## 数据规模与约定
$1 \le n \le 1,000,000$
## 题目来源
第 11 届蓝桥杯青少组 C++ 选拔赛中级组