Немногие знают, что Пан и Аполлон боролись не только за звание лучшего музыканта всех времен. Несколько тысячелетий спустя они также бросили друг другу вызов в математике (или скорее в быстрых вычислениях). Им предстояло решить следующую задачу:
Рассмотрим \(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\).
Выходные данные
Выведите \(t\) строк, \(i\)-я должна содержать ответ на \(i\)-й набор входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2
1 7
3
1 2 4
4
5 5 5 5
5
6 2 2 1 0
1
0
1
1
6
1 12 123 1234 12345 123456
5
536870912 536870911 1152921504606846975 1152921504606846974 1152921504606846973
|
128
91
1600
505
0
1
502811676
264880351
|