Fox Ciel studies number theory.

She thinks a non-empty set S contains non-negative integers is perfect if and only if for any <image> (a can be equal to b), <image>. Where operation xor means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than k. The answer can be very large, so print it modulo 1000000007 (109 + 7).

Input

The first line contains an integer k (0 ≤ k ≤ 109).

Output

Print a single integer — the number of required sets modulo 1000000007 (109 + 7).

Examples

Input

1


Output

2


Input

2


Output

3


Input

3


Output

5


Input

4


Output

6

Note

In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero.

In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 3}.
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.Scanner;

public class ProblemD {
    static final long MOD = 1000000007;
    static long[][] C;
    static int k;

    static long make0(int len) {
        if (len == 0) return 1;
        return 1L << (len-1);
    }

    static long make1(int len) {
        if (len == 0) return 0;
        return 1L << (len-1);
    }

    static long[][][] memo;

    static long solve(int bitPos, int used, int lessFlag) {
        if (bitPos < 0) return 1;
        if (memo[bitPos][used][lessFlag] != -1) return memo[bitPos][used][lessFlag];

        int have = (k & (1<<bitPos)) > 0 ? 1 : 0;

        long ans = 0;

        ans += make0(used) * solve(bitPos - 1, used, have == 1 ? 1 : lessFlag);
        ans %= MOD;

        if (have == 1 || lessFlag == 1) {
            ans += make1(used) * solve(bitPos - 1, used, lessFlag);
            ans %= MOD;

            ans += solve(bitPos - 1, used + 1, lessFlag);
            ans %= MOD;
        }

        memo[bitPos][used][lessFlag] = ans;

        return ans;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new InputStreamReader(System.in));
        k = sc.nextInt();

        memo = new long[30][30][2];
        for (int i=0; i<30; i++) for (int j=0; j<30; j++) memo[i][j][0] = memo[i][j][1] = -1;
        System.out.println(solve(29, 0, 0));
    }
}
