Tanya, Balls, and <<Exclusive Or>>

Tanya had $n$ balls, numbered from $1$ to $n$. Unfortunately, Tanya dropped all the balls into a river and became very upset.

To comfort her, her older brother Seryozha suggested a fun mathematical pastime to Tanya: compute the sum of the pairwise exclusive or of her ball numbers.

The exclusive or of two numbers is denoted $\oplus$ and corresponds to the <<xor>> operation in Pascal or <<\char 94>> in other languages. To compute $x \oplus y$ for two integers, do the following: write each number in binary, and set the $i$-th bit of the result to one if that bit is one in exactly one of $x$ and $y$. For example, $3 \oplus 2 = 11_2 \oplus 10_2 = 1_2 = 1$, $17 \oplus 5 = 10001_2 \oplus 101_2 = 10100_2 = 20$.

Help Tanya! Compute the sum over all pairs of her balls of the exclusive or of their numbers. Tanya does not like large numbers, so the answer must be printed modulo $10^9 + 7$.

For example, if Tanya had $3$ balls, the desired value is $(1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) = 3 + 2 + 1 = 6$.

The first line contains the number $n$, the number of balls Tanya has ($1 \le n \le 10^9$).

Print the sum over all pairs of her balls of the exclusive or of their numbers, taken modulo $10^9 + 7$.