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 <map>
using namespace std;
#define MOD 1000000007

map<pair<long long, long long>, long long> dp;
long long func(long long S, long long X){
    if(dp.count(make_pair(S, X))) return dp[make_pair(S, X)];
    long long &r = dp[make_pair(S, X)];
    if(S == 0){
        r = 1;
        return 1;
    }
    if(X == 0){
        int i = 0;
        while(S != 0){
            S >>= 1;
            i++;
        }
        r = i;
        return i;
    }

    long long d = func(S/2, X/2);
    if(S>=1&&X>=1)
        d = (d+func((S-1)/2, (X-1)/2))%MOD;
    if(S>=2)
        d = (d+func((S-2)/2, X/2))%MOD;
    r = d;
    return d;
}

int main(){
    long long N;
    cin >> N;
    cout << func(N, N) << endl;
	return 0;
}