# 斐波那契

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

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

**输入格式**

输入包含一个整数n。  

输出格式  

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

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

**样例输入**

```
10
```

**样例输出**

```
55
```

**样例输入**

```
22
```

**样例输出**

```
7704
```

**数据规模与约定**

```
1 <= n <= 1,000,000。
```

下列哪一个选项会超时？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
int fib(int n)
{
    if (n < 3)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}
int main()
{
    int n;
    cin >> n;
    cout << fib(n) % 10007 << endl;
    return 0;
}
```
## 选项


### A

```c
int fib(int N)
{
    if (N <= 0)
        return 0;
    if (N == 1 || N == 2)
        return 1;
    int a = 1, b = 1;
    for (int i = 3; i <= N; i++)
    {
        int c = (a + b) % 10007;
        a = b;
        b = c;
    }
    return b;
}
int main()
{
    int n;
    cin >> n;

    cout << fib(n) << endl;

    return 0;
}
```

### B

```c
int main()
{
    int n, b;
    scanf("%d", &n);
    int a[n];
    a[0] = a[1] = 1;

    for (int i = 2; i < n; i++)
    {
        a[i] = (a[i - 1] + a[i - 2]) % 10007;
        b = a[i];
    }
    if (n > 2)
        printf("%d", b);
    else
        printf("1");
    return 0;
}
```

### C

```c
int f[1000000 + 1];

void meter(int n)
{
    f[1] = 1;
    f[2] = 1;
    if (n >= 3)
        for (int i = 3; i <= n; i++)
        {
            f[i] = (f[i - 1] + f[i - 2]) % 10007;
        }
}
int main()
{
    meter(1000000);
    int n;
    cin >> n;
    cout << f[n];
    return 0;
}
```