Jaccard Similarity Sum

Farmer John has N ($1\le N\le 5\cdot10^5$) cows. Each cow is assigned a nonzero binary string of length K ($1\le K\le 20$). (Note that different cows may be assigned the same bit string.)

The Jaccard similarity of two bit strings is defined as follows. Let the similarity between bit strings \(S\) and \(T\) be \[ J(S,T)=\frac{\text{number of 1's in }(S\,\&\,T)}{\text{number of 1's in }(S\,|\,T)}. \] For example, the Jaccard similarity of 11001 and 11010 is \[ \frac{2}{4}. \]

For each cow, compute the sum of the Jaccard similarities between her bit string and the bit string of every cow (including herself) modulo \(10^9+7\). In other words, if the sum is equal to a rational number \(\frac{a}{b}\) in lowest terms, output the unique integer \(x\) in the range \([0,10^9+7)\) such that

[ bx \equiv a \pmod{10^9+7},]

where the modular inverse of \(b\) exists (note that \(b\) and \(10^9+7\) are coprime because the answer is unique).

Note: The memory limit for this problem is 512MB, which is typically twice the normal limit.

inputFormat

The first line contains two integers, N and K.

Then follow N lines, each containing a binary string of length K (with at least one '1').

outputFormat

Output N lines. The i-th line should contain the answer for the i-th cow (in the order of input): the sum of its Jaccard similarities with every cow’s bit string, given as an integer as described above.

sample

3 5
11001
11010
01010

750000007
166666670
916666675