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.*;
import java.util.*;

public class Main implements Runnable {

	public void _main() throws IOException {
		final int N = 31;
		final int MOD = 1000000007;
		int k = nextInt();
		int[] p2 = new int[N];
		p2[0] = 1;
		for (int i = 1; i < p2.length; i++) {
			p2[i] = 2 * p2[i - 1] % MOD;
		}
		long[][][] d = new long[N][N][2];
		d[N - 1][0][1] = 1;
		for (int i = N - 1; i > 0; i--) {
			int bit = (k >> (i - 1)) & 1;
			for (int inBasis = 0; inBasis < N; inBasis++) {
				for (int eq = 0; eq < 2; eq++) {
					long cur = d[i][inBasis][eq];
					if (bit == 1 || eq == 0) {
						if (inBasis + 1 < N) {
							d[i - 1][inBasis + 1][eq] = (d[i - 1][inBasis + 1][eq] + cur) % MOD;
						}
					}
					if (inBasis == 0) {
						int neq = 1;
						if (bit == 1 || eq == 0) {
							neq = 0;
						}
						d[i - 1][inBasis][neq] = (d[i - 1][inBasis][neq] + cur) % MOD;
						continue;
					}
					// 1
					if (bit == 1 || eq == 0) {
						d[i - 1][inBasis][eq] = (d[i - 1][inBasis][eq] + cur*p2[inBasis - 1]) % MOD;
					}
					// 0
					int neq = 1;
					if (bit == 1 || eq == 0) {
						neq = 0;
					}
					d[i - 1][inBasis][neq] = (d[i - 1][inBasis][neq] + cur*p2[inBasis - 1]) % MOD;
				}
			}
		}
		long ans = 0;
		for (int inBasis = 0; inBasis < N; inBasis++) {
			for (int eq = 0; eq < 2; eq++) {
				ans = (ans + d[0][inBasis][eq]) % MOD;
			}
		}
		out.println(ans);
	}


	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;

	private String next() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String rl = in.readLine();
			if (rl == null)
				return null;
			st = new StringTokenizer(rl);
		}
		return st.nextToken();
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public static void main(String[] args) {
		Locale.setDefault(Locale.UK);
		new Thread(new Main()).start();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			//in = new BufferedReader(new FileReader("a.in"));
			//out = new PrintWriter(new FileWriter("a.out"));

			_main();

			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(202);
		}
	}

}
