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.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author sheep
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    private static final int MOD = 1000000007;
    private long odd(int x) {
        if (x == 0) {
            return 0;
        }
        return (1 << (x - 1));
    }
    private long even(int x) {
        return (1 << (x)) - odd(x);
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int k = in.nextInt();
        // dp[full set][num]
        int[][] dp = new int[2][35];
        dp[1][0] = 1;
        for (int i = 30; i >= 0; --i) {
            int[][] next = new int[2][35];
            int bit = (k >> i) % 2;
            if (bit == 0) {
                for (int num = 0; num < 32; ++num) {
                    next[1][num] = (int) ((next[1][num] + dp[1][num] * even(num)) % MOD);
                }
            } else {
                for (int num = 0; num < 32; ++num) {
                    next[1][num] = (int) ((next[1][num] + dp[1][num] * odd(num)) % MOD);
                    next[0][num] = (int) ((next[0][num] + dp[1][num] * even(num)) % MOD);
                }

                for (int num = 0; num < 32; ++num) {
                    next[1][num + 1] = (int) ((next[1][num + 1] + dp[1][num]) % MOD);
                }
            }

            for (int num = 0; num < 32; ++num) {
                next[0][num + 1] = (int) ((next[0][num + 1] + dp[0][num]) % MOD);
                next[0][num] = (int) ((next[0][num] + dp[0][num] * (1L << (long) num)) % MOD);
            }

            dp = next;
//            print(dp);
//            System.err.println("====");
        }

        long answer = 0;
        for (int i = 0; i < 32; ++i) {
            answer = (answer + dp[0][i] + (long) dp[1][i]) % MOD;
        }

        out.println(answer);
    }
}

class InputReader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (Exception e) {
                throw new UnknownError();
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    }
