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 <string.h>
#include <map>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

ll n;
ll p3[65];
map<pair<ll,int>,ll> dp;

ll dfs(ll n,int i) {
    if (dp.find(mp(n,i))!=dp.end()) {
        return dp[mp(n,i)];
    }
    if (n<0) return 0;
    if (i==0) return 1;
    ll tot=(1LL<<(i+1))-2;
    if (n>=tot) return dp[mp(n,i)]=p3[i];
    ll a=dfs(n,i-1);
    ll b=dfs(n-(1LL<<(i-1)),i-1);
    ll c=dfs(n-(1LL<<i),i-1);
    return dp[mp(n,i)]=(a+b+c)%MOD;
}

int main() {
    scanf("%lld",&n);
    memset(p3,0,sizeof(p3));
    p3[0]=1;
    for (int i=1;i<=60;i++) {
        p3[i]=p3[i-1]*3;
        p3[i]=p3[i]%MOD;
    }
    ll ans=dfs(n,60);
    printf("%lld\n",ans);
}