Задача №114853. Таня, мячи и <<исключающее или>>
У Тани было n мячей, она пронумеровала их от 1 до n . Но, к сожалению, Таня уронила все мячи в реку и сильно расстроилась.
Чтобы утешить ее, старший брат Сережа предложил Тане забавное математическое развлечение: посчитать сумму попарных исключающих или от номеров ее мячей.
Исключающее или двух чисел обозначается как
и соответствует операции «
xor
» в паскале или «
^
» в других языках. Чтобы вычислить
для двух целых чисел, необходимо сделать следующее: представить каждое из чисел в двоичной системе счисления и сделать
i
-й разряд результата единицей, если он равен единице ровно в одном из чисел
x
и
y
. Например,
,
.
Помогите Тане! Посчитайте сумму по всем парам ее мячей исключающих или их номеров. Таня не любит большие числа, так что ответ необходимо вывести по модулю 10 9 + 7 .
Например, если у Тани было
3
мяча, то искомое значение равно
.
В первой строке задано число n — количество мячей у Тани ( 1 ≤ n ≤ 10 9 ).
Выведите сумму по всем парам ее мячей исключающих или их номеров, взятую по модулю 10 9 + 7 .
3
6