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<bits/stdc++.h>
#include<iomanip>

using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;
constexpr ll md = mod;
constexpr ll inf = 1e15;
int main(){
    ll n;
    cin>>n;
    vector<vector<ll>> dp(62,vector<ll>(3));
    bitset<60> bs(n);
    dp[0][0] = 1;
    for(int i=0;i<=60;i++){
        if(bs[60-i]){
            dp[i+1][0] += dp[i][0];
            (dp[i+1][1] += dp[i][1] + dp[i][0])%= mod;
            (dp[i+1][2] += dp[i][2]*3%mod + dp[i][1]*2%mod)%= mod;
        }else{
            (dp[i+1][0] += dp[i][0] + dp[i][1] )%= mod;
            dp[i+1][1] += dp[i][1];
            (dp[i+1][2] += dp[i][1] + dp[i][2] * 3 %mod)%= mod;
        }
    }
    cout << ((dp[61][0] + dp[61][1])%mod + dp[61][2])%mod << endl;
    return 0;
}

