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>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

ll N;
vector<int> A;

int cc[62][2][2][2];
int dp(int n, int t, int d, int c) {
    if(n == A.size()) return t == 0 && d == 0 && c == 0;
    int &ret = cc[n][t][d][c];
    if(ret != -1) return ret;

    ret = 0;
    int x = A[n];
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            if(i == 0 && j == 1) continue;

            int nt = ((i ^ j) > x) || (t & (i ^ j) == x);
            int nd = ((i + j + c) % 2 > x) || (d & (i + j + c) % 2 == x);

            ret += dp(n + 1, nt, nd, (i + j + c) / 2);
            ret %= mod;
        }
    }
    return ret;
}

int main() {
    cin >> N;

    while(N) {
        A.push_back(N % 2);
        N /= 2;
    }

    memset(cc, -1, sizeof(cc));
    printf("%d", dp(0, 0, 0, 0));
}
