Shared code

#include<iostream>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
//#include<algorithm>

#define endl "\n"
#define form(i,m,n) for(int i=(m);i<(n);i++)
#define forn(i,n) form(i,0,n)
#define dfor(i,n) for(int i = n;i-->0;)
#define len(n) ((int)n.size())
#define $ <<" "<<
#define printv(v) if(1){for(auto _ : v) cerr << _ << " "; cerr << endl;}

using namespace std;
typedef long long ll;
const ll INF = 1e10;
const ll mod = 1e9+7;

unordered_map<int, int> memo;
ll fib(ll n){
  if(memo.count(n)) return memo[n];
  // n/2 = k
  // f(n) = f(k)*f(n-k)+f(k-1)*f(n-1-k)
  ll k = n/2;
  return memo[n] = ((fib(k)*fib(n-k))%mod + (fib(k-1) * fib(n-1-k))%mod)%mod;
}

int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  ll n;
  cin >> n;
  memo[-1] = 0;
  memo[0] = 1;
  memo[1] = 1;
  cout << fib(n-1) << endl;
  //for(auto [i,j] : memo) cout << i $ j << endl;
}