Каждой из $N$ ($1\le N\le 5\cdot 10^5$) коров Farmer John назначена битовая строка длины $K$, не состоящая только из нулей ($1\le K\le 20$). Разным коровам может быть назначена одинаковая битовая строка.

Сходство Jaccard двух битовых строк определяется как количество единичных битов в их побитовом пересечении, делённое на количество единичных битов в их побитовом объединении. Например, сходство Jaccard строк $\texttt{11001}$ и $\texttt{11010}$ равно $2/4$.

Для каждой коровы выведите сумму сходств Jaccard её битовой строки с битовыми строками каждой из $N$ коров, включая её собственную, по модулю $10^9+7$. А именно, если сумма равна рациональному числу $a/b$, где $a$ и $b$ — взаимно простые целые числа, выведите единственное целое число $x$ из диапазона $[0,10^9+7)$, для которого $bx-a$ делится на $10^9+7$.

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

Первая строка содержит $N$ и $K$. Каждая из следующих $N$ строк содержит целое число $i\in (0,2^K)$, представляющее корову, которой соответствует двоичная запись числа $i$ длины $K$.

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

Для каждой коровы выведите сумму по модулю $10^9+7$ в отдельной строке.

Примеры

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

4 2
1
1
2
3

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

500000006
500000006
500000005
500000006

Примечание

Коровам соответствуют следующие битовые строки: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Для первой коровы сумма равна $\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006\pmod{10^9+7}$. Битовая строка второй коровы совпадает со строкой первой, поэтому её сумма такая же. Для третьей коровы сумма равна $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.

Для первой коровы сумма равна $\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006\pmod{10^9+7}$. Для третьей коровы сумма равна $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.

Битовая строка второй коровы совпадает со строкой первой, поэтому её сумма такая же. Для третьей коровы сумма равна $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.

Для третьей коровы сумма равна $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.

Ограничения

Входные группы 2-15: для каждого $K\in \{10,15,16,17,18,19,20\}$ будет по два тестовых случая.