A9298 | 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$ $(10^{9}+7)$ .

The first line contains an integer $k$ ( $0<=k<=10^{9}$ ).

Print a single integer — the number of required sets modulo $1000000007$ $(10^{9}+7)$ .