Задача №113326. Таня, мячи и «исключающее или»
У Тани было \(n\) мячей, она пронумеровала их от \(1\) до \(n\). Но, к сожалению, Таня уронила все мячи в реку и сильно расстроилась.
Чтобы утешить ее, старший брат Сережа предложил Тане забавное математическое развлечение: посчитать сумму попарных исключающих или от номеров ее мячей.
Исключающее или двух чисел обозначается как \(\oplus\) и соответствует операции «xor» в паскале или «^» в других языках. Чтобы вычислить 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\).