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
/**
 * 方針:
 * a, b の各 bit に (0, 0), (0, 1), (1, 1) のどのパターンを置いていくかを決めていくことを考えればよい．
 * これでありうる (u, v) は網羅できることは明らかで，重複しないことも容易に示すことが出来る．
 * 
 * a ^ b <= a + b なので，a + b <= N を満たすように桁 DP をすれば良さそう．ただ，(1, 1) を選べるので状態が少し複雑になる．
 * 
 * どのような状態があるのかを考える．以下，N の i bit 目を N[i] と表すことにする．
 * また，i + 1 bit 目まででの a + b の値を X[i+1] とする．
 * 
 * 状態 A: X[i+1] + Σ[k=0,i] N[k]*2^k == N （最もタイトな場合）
 *          この時，N[i] = 0, 1 のそれぞれで (0, 0), (0, 1), (1, 1) を選んだ場合に移る状態を考える．
 *           (i) N[i] = 1
 *              (0, 0) を選んだ場合: X[i] + 2^i <= N となる．新しい状態なので，この状態を状態 B' としておく．
 *              (0, 1) を選んだ場合: X[i] + Σ[k=0,i-1] N[k]*2^k == N となり，これは状態 A と一致する．
 *              (1, 1) は X[i] > N となるので不適当．
 *          (ii) N[i] = 0
 *              (0, 0) を選んだ場合: X[i] + Σ[k=0,i-1] N[k]*2^k == N となり，これは状態 A と一致する．
 *              (0, 1), (1, 1)  は X[i] > N となるので不適当．
 * 状態 B': X[i+1] + 2^(i+1) <= N
 *           (i) N[i] = 1
 *              (0, 0) を選んだ場合: X[i] + Σ[k=0,i-1] 2*(2^i-1) <= N となり，以降はどのペアも自由に選ぶことが出来る．これを状態 C とする．
 *              (0, 1) を選んだ場合: X[i] + Σ[k=0,i-1] 2*(2^i-1) <= N となり，これは状態 C と一致する．
 *              (1, 1) を選んだ場合: X[i] + 2^i <= N となり，これは状態 B' と一致する．
 *          (ii) N[i] = 0
 *              (0, 0) を選んだ場合: X[i] + Σ[k=0,i-1] 2*(2^i-1) <= N となり，これは状態 C と一致する．
 *              (0, 1) を選んだ場合: X[i] + 2^i <= N となり，これは状態 B' と一致する．
 *              (1, 1) を選んだ場合: X[i] + Σ[k=0,i-1] N[k]*2^k <= N となる．等号が成立すれば状態 A と一致するが...
 *                                  ここで，状態 B として X[i+1] + 2^(i+1) == N としても今までの議論が成立することに気付く．
 *                                  これによって，遷移先を状態 A に確定することが出来た．
 * 状態 C: X[i+1] + Σ[k=0,i] 2*(2^(i+1)-1) <= N
 *          どのペアを選んでも X[i] + Σ[k=0,i-1] 2*(2^i-1) <= N となるので遷移先は状態 C である．
 * 
 * 以上で定めた状態 A，B，C を用いると，桁 DP が出来る．ここまで分かれば実装も難しい点は無い．
 */
public class Main {
    public static void main(String[] args) {
        var sc = new java.util.Scanner(System.in);
        long n = sc.nextLong();
        sc.close();
        boolean[] nBits = new boolean[60];
        for (int i = 0; i < 60; i++) nBits[i] = (n & (1l << i)) != 0;
        final long MOD = 1000000007;
        long[] dpA = new long[61];
        long[] dpB = new long[61];
        long[] dpC = new long[61];
        dpA[60] = 1;
        for (int i = 59; i >= 0; i--) {
            if (nBits[i]) {
                // 状態 A からの遷移
                dpB[i] += dpA[i + 1]; // (0, 0): A -> B
                dpA[i] += dpA[i + 1]; // (0, 1): A -> A
                // 状態 B からの遷移
                dpC[i] += dpB[i + 1]; // (0, 0): B -> C
                dpC[i] += dpB[i + 1]; // (0, 1): B -> C
                dpB[i] += dpB[i + 1]; // (1, 1): B -> B
                // 状態 C からの遷移
                dpC[i] += dpC[i + 1]; // (0, 0): C -> C
                dpC[i] += dpC[i + 1]; // (0, 1): C -> C
                dpC[i] += dpC[i + 1]; // (1, 1): C -> C
            } else {
                // 状態 A からの遷移
                dpA[i] += dpA[i + 1]; // (0, 0): A -> A
                // 状態 B からの遷移
                dpC[i] += dpB[i + 1]; // (0, 0): B -> C
                dpB[i] += dpB[i + 1]; // (0, 1): B -> B
                dpA[i] += dpB[i + 1]; // (1, 1): B -> A
                // 状態 C からの遷移
                dpC[i] += dpC[i + 1]; // (0, 0): C -> C
                dpC[i] += dpC[i + 1]; // (0, 1): C -> C
                dpC[i] += dpC[i + 1]; // (1, 1): C -> C
            }
            dpA[i] %= MOD;
            dpB[i] %= MOD;
            dpC[i] %= MOD;
        }
        long ans = dpA[0] + dpB[0] + dpC[0];
        System.out.println(ans % MOD);
    }
}