CF388D.Fox and Perfect Sets

Fox Ciel studies number theory.

She thinks a non-empty set S contains non-negative integers is perfect if and only if for any (a can be equal to b), . 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).

Fox Ciel 正在学习数论。

她认为，一个非空集合 $ S $（其元素为非负整数）是“完美”的，当且仅当对任意 $ a, b \in S $（$ a $ 可以等于 $ b $），都有 $ a \oplus b \in S $。其中运算 $ \oplus $ 表示异或运算（http://en.wikipedia.org/wiki/Exclusive_or）。

请计算由不超过 $ k $ 的整数组成的完美集合的个数。答案可能非常大，因此请输出其对 $ 1000000007 $（即 $ 10^9 + 7 $）取模的结果。

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

第一行包含一个整数 $k$（$0 \le k \le 10^9$）。

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

输出一个整数——所需集合的数量对 1000000007（$10^9 + 7$）取模的结果。

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}.

在示例 1 中，存在 2 个这样的集合：{0} 和 {0, 1}。注意，{1} 不是完美集合，因为 $1 \oplus 1 = 0$，而 {1} 并不包含 0。

在示例 4 中，存在 6 个这样的集合：{0}、{0, 1}、{0, 2}、{0, 3}、{0, 4} 和 {0, 1, 2, 3}。