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>
#define int long long
using namespace std;

std::vector<int> v(61),w(61);
const int INF=1e9+7;
int dp[600000][50];
int dfs(int S,int X){
  if(S<600000&&S>=0&&X<=50&&X>=0){
    int &res=dp[S][X];
    if(res!=-1)return res;
    if(S<0){res=0;return res;}
    if(S>(v[X]-1)*2){res=w[X];return res;}
    if(S==0&&X==0){res=1;return res;}
    res=(dfs(S,X-1)+dfs(S-v[X-1],X-1)+dfs(S-v[X],X-1))%INF;return res;
  }
  else{
    int res;
    if(S<0){res=0;return res;}
    if(S>(v[X]-1)*2){res=w[X];return res;}
    if(S==0&&X==0){res=1;return res;}
    res=(dfs(S,X-1)+dfs(S-v[X-1],X-1)+dfs(S-v[X],X-1))%INF;return res;
  }
}

signed main(){
  v[0]=1;for(int i=1;i<61;i++)v[i]=v[i-1]*2;
  w[0]=1;for(int i=1;i<61;i++)w[i]=w[i-1]*3%INF;
  memset(dp,-1,sizeof(dp));
  int N;
  cin>>N;
  cout<<dfs(N,60)<<endl;
}
