E. Аполлон против Пана
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Немногие знают, что Пан и Аполлон боролись не только за звание лучшего музыканта всех времен. Несколько тысячелетий спустя они также бросили друг другу вызов в математике (или скорее в быстрых вычислениях). Им предстояло решить следующую задачу:

Рассмотрим $$$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$$$ ($$$1 \leq t \leq 1\,000$$$), обозначающее количество наборов входных данных. Затем дано $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), длина последовательности. Во второй строке дано $$$n$$$ неотрицательных целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \leq x_i < 2^{60}$$$), элементы последовательности.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^5$$$.

Выходные данные

Выведите $$$t$$$ строк, $$$i$$$-я должна содержать ответ на $$$i$$$-й набор входных данных.

Пример
Входные данные
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