**Замечание:
Ограничение по памяти для этой задачи 512MB, в два раза больше чем по умолчанию.**
Каждой из \(N\) (\(1\le N\le 5\cdot 10^5\)) коров Фермера Джона назначена ненулевая
битовая строка длиной \(K\) (\(1\le K\le 20\)). Различным коровам может быть
назначена одинаковая битовая строка.
Сходство Жаккара двух битовых строк определяется как количество (?единичных) битов
в их пересечении, делённое на количество (?единичных) битов в их объединении.
Например, сходство Жаккара битовых строк \(\texttt{11001}\) и \(\texttt{11010}\)
равно \(2/4\).
Для каждой коровы выведите сумму сходств Жаккара её с битовыми строками
всех других коров, включая её саму, по модулю \(10^9+7\). Точнее если сумма
равна рациональному числу \(a/b\), где \(a\) и \(b\) целые числа, не имеющие общих
делителей, выведите уникальное целое число \(x\) в интервале \([0,10^9+7)\)
такое, что \(bx-a\) делится на \(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(K\).
Каждая из следующих \(N\) строк содержит целое число \(i\in (0,2^K)\),
представляющее корову, ассоциированную с \(K\)-битовым представлением числа \(i\).
ФОРМАТ ВЫВОДА (на экран / stdin):
Выведите сумму по модулю \(10^9+7\) для каждой коровы на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1
1
2
3
|
500000006
500000006
500000005
500000006
|