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

제한

힌트