inline long long int dfs(long long int b){
	if (b == 0){
		return 1;
	}
	if (b == 1){
		return 3;
	}
	if (b == 2){
		return 4;
	}
	if (b == 3){
		return 7;
	}
	if (b == 4){
		return 9;
	}
	if (b % 2 == 0){
		long long int NN = b / 2;
		return ((dfs(NN - 2)) + (2LL * dfs(NN - 1)) + 2LL)%MOD;
	}
	return (2LL * dfs((b - 3) / 2LL) + dfs((b - 1LL) / 2LL)+2LL)%MOD;
}
lnog long in
int main(){
	long long int f;
	scanf("%lld", &f);
	printf("%lld\n", dfs(f)+1LL);
	return 0;
}