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 <map>
using namespace std;
const long long MOD = 1e9 + 7;

map<pair<long long, int>, long long> mm;

long long solve(long long N, int b)
{
  if (N < 0)
    return 0LL;
  if (b == -1)
    return 1LL;
  if (N > 4LL * (1LL << b))
    N = 4LL * (1LL << b);
  //cout << N << " " << b << endl;
  if (mm[{N, b}] != 0)
    return mm[{N, b}];
  mm[{N, b}] = (solve(N, b - 1) + solve(N - (1LL << b), b - 1) + solve(N - 2LL * (1LL << b), b - 1)) % MOD;
  return mm[{N, b}];
}

int main()
{
  long long n;
  cin >> n;
  cout << solve(n, 60);
}