20分

#include<iostream>
using namespace std;
long long n,x[2][2],R=1000000007;
void fibonacci(long long t)
{
    long long p[2][2];
    if(t==1)
    {
        x[0][0]=x[0][1]=x[1][0]=1;
        x[1][1]=0;
        return;
    }
    fibonacci(t/2);
    p[0][0]=(x[0][0]*x[0][0])%R+(x[0][1]*x[1][0])%R;
    p[0][1]=(x[0][0]*x[0][1])%R+(x[0][1]*x[1][1])%R;
    p[1][0]=(x[1][0]*x[0][0])%R+(x[1][1]*x[1][0])%R;
    p[1][1]=(x[1][0]*x[0][1])%R+(x[1][1]*x[1][1])%R;
    x[0][0]=p[0][0],x[0][1]=p[0][1];
    x[1][0]=p[1][0],x[1][1]=p[1][1];
    if(t%2==1)
    {
        p[0][0]=(x[0][0]+x[0][1])%R,p[0][1]=x[0][0];
        p[1][0]=(x[1][0]+x[1][1])%R,p[1][1]=x[1][1];
        x[0][0]=p[0][0],x[0][1]=p[0][1];
        x[1][0]=p[1][0],x[1][1]=p[1][1];
    }
    return;
}
int main()
{
    cin>>n;
    if(n<=2)  return cout<<1,0;
    return fibonacci(n-2),cout<<(x[0][0]+x[1][0])%R,0;
}