Немногие знают, что Пан и Аполлон боролись не только за звание лучшего музыканта всех времен. Несколько тысячелетий спустя они также бросили друг другу вызов в математике (или скорее в быстрых вычислениях). Им предстояло решить следующую задачу:
Рассмотрим \(x_1, x_2, \ldots, x_n\) — последовательность из \(n\) неотрицательных целых чисел. Вычислите следующее значение: \(\)\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k)\(\)
Здесь \(\&\) обозначает побитовый И, а \(|\) обозначает побитовый ИЛИ.
Пан и Аполлон смогли решить эту задачу за несколько секунд. А вы сможете? Для удобства, вычислите ответ по модулю \(10^9 + 7\).