80分

code:

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

#define ll long long

const int N=1e5+5;
const int M=1e3+5;
const ll MOD=1e9 + 7;

struct node
{
    ll a,b;
};
ll n, m;

node solve(int num)
{
    node x, y;
    if (num == 1)
    {
        x.a = 1, x.b = 0;
        return x;
    }
    y = solve(num/2);
    x.a = y.a * y.a + 2 * y.a * y.b;
    x.a %= MOD;
    x.b = y.b * y.b + y.a * y.a;
    x.b %= MOD;
    if (num & 1)
    {
        ll c = x.a + x.b;
        x.b = x.a, x.a = c;
    }
    return x;

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    cout<< solve(n).a % MOD<<endl;
    return 0;
}