#include <bits/stdc++.h>
#define ll long long
#define int unsigned long long 
using namespace std;
const int mod=1e9+7;
map<int , int >a;
string s;
int f(int x){
	if(x==1||x==2){
		return 1;
	}
	if(a[x])return a[x]%mod;
	else{
		int c=f(x>>1)%mod;
		if(x%2==0){
			a[x]=((f(x-2>>1)<<1)+c)%mod*c%mod;
			return a[x];
		}
		else{
			int b=f(x+1>>1)%mod*2%mod;
			a[x]=(b*b%mod+c*c%mod)%mod;
			return a[x];
		}
	}
}
signed main() {
	a[1]=1;
	a[2]=1;
	a[3]=2;
	int n;
	cin>>n;
	cout<<f(n)%mod;
	return 0;	
}