All Pairs Similarity

문제

Farmer John's $NN$ ($1\le N\le 5\cdot {10}^{5}1\backslash le\; N\backslash le\; 5\backslash cdot\; 10^5$) cows are each assigned a bitstring of length $KK$ that is not all zero ($1\le K\le 201\backslash le\; K\backslash le\; 20$). Different cows may be assigned the same bitstring.

The Jaccard similarity of two bitstrings is defined as the number of set bits in their bitwise intersection divided by the number of set bits in their bitwise union. For example, the Jaccard similarity of the bitstrings 11001 and 11010 would be $2\mathrm{/}42/4$.

For each cow, output the sum of her bitstring's Jaccard similarity with each of the $NN$ cows' bitstrings including her own, modulo ${10}^9+710^9+7$. Specifically, if the sum is equal to a rational number $a\mathrm{/}ba/b$ where $aa$ and $bb$ are integers sharing no common factors, output the unique integer $xx$ in the range $[0,{10}^9+7)[0,10^9+7)$ such that $bx-abx-a$ is divisible by ${10}^9+710^9+7$.

입력

The first line contains $NN$ and $KK$.

The next $NN$ lines each contain an integer $i\in (0,2^K)i\backslash in\; (0,2^K)$, representing a cow associated with the length-$KK$ binary representation of $ii$.

출력

Output the sum modulo ${10}^9+710^9+7$ for each cow on a separate line.

힌트

The cows are associated with the following bitstrings: $[[$01, 01, 10, 11$]]$.

For the first cow, the sum is $\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1\mathrm{/}2\equiv 500000006(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)\backslash text\{sim\}(1,1)+\backslash text\{sim\}(1,1)+\backslash text\{sim\}(1,2)+\backslash text\{sim\}(1,3)=1+1+0+1/2\backslash equiv\; 500000006\backslash pmod\{10^9+7\}$.

The second cow's bitstring is the same as the first cow's, so her sum is the same as above.

For the third cow, the sum is

$\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1\mathrm{/}2\equiv 500000005(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)\backslash text\{sim\}(2,1)+\backslash text\{sim\}(2,1)+\backslash text\{sim\}(2,2)+\backslash text\{sim\}(2,3)=0+0+1+1/2\backslash equiv\; 500000005\backslash pmod\{10^9+7\}$.

4 2
1
1
2
3

500000006
500000006
500000005
500000006