You are given a positive integer N. Find the number of the pairs of integers u and v (0≦u,v≦N) such that there exist two non-negative integers a and b satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR. Since it can be extremely large, compute the answer modulo 10^9+7.

Constraints

* 1≦N≦10^{18}

Input

The input is given from Standard Input in the following format:


N


Output

Print the number of the possible pairs of integers u and v, modulo 10^9+7.

Examples

Input

3


Output

5


Input

1422


Output

52277


Input

1000000000000000000


Output

787014179

#include "iostream"
#include "vector"
#include "algorithm"
#include "map"
typedef long long i64;

i64 n;
i64 MODULO = (i64)(1e9 + 7);

std::map<i64, std::map<i64, i64>> map;

i64 f(i64 x, i64 y) {
	if (x == 0 && y == 0)
		return 1;
	if (x < 0 || y < 0)
		return 0;
	i64& ret = map[x][y];
	if (ret != 0)return ret;
	ret += f(x >> 1, y >> 1);
	ret += f((x - 1) >> 1, (y - 1) >> 1);
	ret += f((x - 2) >> 1, y >> 1);
	ret %= MODULO;
	return ret%MODULO;
}

int main() {
	std::cin >> n;
	std::cout << f(n, n);
	return 0;
}


