All Pairs Similarity

Farmer John has $N$ cows ($1\le N\le 5\cdot 10^5$), and each cow is assigned a bitstring of length $K$ that is not all zero ($1\le K\le 20$). Different cows may be assigned the same bitstring. The Jaccard similarity of two bitstrings is 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 is $2/4$. For each cow, output the sum of her bitstring's Jaccard similarity with the bitstrings of all $N$ cows, including her own, modulo $10^9+7$. If the sum equals a rational number $a/b$ with $a$ and $b$ coprime, output the unique integer $x$ in $[0, 10^9+7)$ such that $bx-a$ is divisible by $10^9+7$.

The first line contains $N$ and $K$. Each of the next $N$ lines contains an integer $i \in (0, 2^K)$, which represents the cow's bitstring as the length-$K$ binary representation of $i$.

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

The cows are assigned the bitstrings 01, 01, 10, and 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+\frac{1}{2}\equiv 500000006 \pmod{10^9+7}$. The second cow has the same bitstring as the first cow, so her sum is the same. 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+\frac{1}{2}\equiv 500000005 \pmod{10^9+7}$.