19762번 - Таня, мячи и <<исключающее или>> 다국어

У Тани было $n$ мячей, она пронумеровала их от $1$ до $n$. Но, к сожалению, Таня уронила все мячи в реку и сильно расстроилась.

Чтобы утешить ее, старший брат Сережа предложил Тане забавное математическое развлечение: посчитать сумму попарных исключающих или от номеров ее мячей.

Исключающее или двух чисел обозначается как $\oplus$ и соответствует операции <<xor>> в паскале или <<\char 94>> в других языках. Чтобы вычислить $x \oplus y$ для двух целых чисел, необходимо сделать следующее: представить каждое из чисел в двоичной системе счисления и сделать $i$-й разряд результата единицей, если он равен единице ровно в одном из чисел $x$ и $y$. Например, $3 \oplus 2 = 11_2 \oplus 10_2 = 1_2 = 1$, $17 \oplus 5 = 10001_2 \oplus 101_2 = 10100_2 = 20$.

Помогите Тане! Посчитайте сумму по всем парам ее мячей исключающих или их номеров. Таня не любит большие числа, так что ответ необходимо вывести по модулю $10^9 + 7$.

Например, если у Тани было $3$ мяча, то искомое значение равно $(1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) = 3 + 2 + 1 = 6$.

В первой строке задано число $n$ --- количество мячей у Тани ($1 \le n \le 10^9$).

Выведите сумму по всем парам ее мячей исключающих или их номеров, взятую по модулю $10^9 + 7$.