资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
样例输入
10
样例输出
55
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
斐波拉契数列是一个很经典的结构（0、1、1、2、3、5、8、13、21、34、……），也引申出了很多问题，先以本道题为例。
（1）递归求解
构造递归函数，每次计算调用该函数，直到算出结果。
···
#include <iostream>
using namespace std;
int f(int n){
return n<=2?1:(f(n-1)+f(n-2))%10007;
}
int main()
{
int n,i;
cin>>n;
cout<<f(n);
return 0;
}
···
但是这个做法运行超时，只得到了30分，原因是递归存在大量的重复运算。
f(5)=f(4)+f(3)=f(3)+f(2)+f(2)+f(1)=f(2)+f(1)+3=5
计算f(5)，f(3)算了2次，f(2)算了3次，f(1)算了2次。
（2）递推求解
用数组表示该数列，利用递推式前项得到后项进行计算得出结果。
···
#include <iostream>
using namespace std;
int main()
{
int n,i;
cin>>n;
int* a=new int [n];
a[0]=1;
a[1]=1;
for(i=2;i<n;i++)
{
a[i]=(a[i-1]+a[i-2])%10007;
}
cout<<a[n-1];
return 0;
}
···
这样已经满足要求了，当然还有更快的方法，参考链接：
https://www.zhihu.com/question/28062458/answer/39763094
另外，还有一些典型的斐波拉契数列问题
有n个台阶，你每次只能跨一阶或两阶，上楼有几种方法？
第一个月初有一对刚诞生的兔子
第二个月之后（第三个月初）它们可以生育
每月每对可生育的兔子会诞生下一对新兔子
兔子永不死去
一年以后可以繁殖多少对兔子？
参考网址：
https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fromtitle=%E6%96%90%E6%B3%A2%E6%8B%89%E5%A5%91%E6%95%B0%E5%88%97&fromid=10078434&fr=aladdin
