小明很喜欢爬楼梯，但是小明腿不够长，每次小明最多只能一步跨越两个阶梯。比如他初始在楼底，跨越一个阶梯到达

1 号阶梯，或者跨越两个阶梯到达

3 号阶梯。

为了选出一种最轻松的爬楼梯的方式，小明想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 n 个阶梯的楼梯，小明一共有多少总方法从楼底到达楼顶。

由于最后答案可能很大，输出最后的答案对 100007 取模的结果。

输入格式 第一行输入一个整数

n (1≤n≤1000)。

输出格式 输出最后答案对于 100007 取模的结果。

代码

#include<iostream>
using namespace std;
long long a[1001];
int main(){
    int n;
    a[1]=1;
    a[2]=1;
    a[3]=2;
    cin>>n;
    for(int i=4;i<=n;i++){
        a[i]=(a[i-1]+a[i-3])%100007;
    }
    cout<<a[n]%100007;
    return 0;
}