ta có thể thấy rằng

~f0=0, f1=1, f2=1, f3=2,f4=3,f5=5,f6=8,f7=13,f8=21~

~s0=0, s1=1, s2=2, s3=4,s4=7,s5=12,s6=20,s7=33,s8=54~

dễ nhận thấy rằng ~s_n=f_{n+2}-1~ với mọi n. cũng có phương pháp đó là chứng minh bằng toán nhưng mình sẽ k làm ở đây

để vét được 50% test đầu, ta có thể dùng dp theo công thức fn=fn-1+fn-2

để ăn được ta sẽ dùng tính nhanh fibonacci, có nhiều cách để làm như là nhân ma trận. nhưng mình sẽ dùng 1 cách khác

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = (int) 1e9 + 7;
map<int,int> fb;
int fibo(int n){
    if(fb.count(n)){
        return fb[n];
    }
    int k=n/2;
    if(n&1){
        return fb[n]=((fibo(k)*fibo(k+1))%mod + (fibo(k-1)*fibo(k))%mod)%mod;
    }
    else {
        return fb[n]=((fibo(k)*fibo(k))%mod + (fibo(k-1)*fibo(k-1))%mod)%mod;;

    }
}

int32_t main(){
    int n;
    fb[0]=fb[1]=1;
    fb[-1]=0;
    cin>>n;
    n--;
    cout<<fibo(n);
}