9AC+1WA

#include <bits/stdc++.h>
#define LL long long int
using namespace std;
const LL mod=1e9+7;
map<LL,LL> mp;
LL f(LL x){
    if(mp.count(x)){
        return mp[x];
    }
    LL s=0;
    if(x&1){
        s=(f((x-1)/2)*f((x-1)/2)%mod+f((x+1)/2)*f((x+1)/2)%mod)%mod;
    }
    else{
        s=f(x/2)*(2*f(x/2+1)%mod-f(x/2)%mod)%mod;
    }
    return mp[x]=s;
}
int main(){
    LL m;
    cin>>m;
    mp[0]=0,mp[1]=mp[2]=1;
    if(mp.count(m)) cout<<mp[m];
    else{
        cout<<(f(m)%mod);
    }
    return 0;
}