모든 쌍의 유사도

농부 존의 소 $N$마리($1\le N\le 5\cdot 10^5$)에게는 각각 길이 $K$인 비트열이 하나씩 할당되어 있다($1\le K\le 20$). 비트열은 모두 0이 아닌 값이다. 서로 다른 소에게 같은 비트열이 할당될 수도 있다. 두 비트열의 자카드 유사도는 비트 AND 결과의 1의 개수를 비트 OR 결과의 1의 개수로 나눈 값이다. 예를 들어 11001과 11010의 자카드 유사도는 $2/4$이다. 각 소에 대해, 자신의 비트열과 자기 자신을 포함한 $N$마리 소의 비트열 각각이 이루는 자카드 유사도를 모두 더한 값을 $10^9+7$로 나눈 나머지로 출력한다. 합이 서로소인 정수 $a$, $b$에 대해 $a/b$이면, $bx-a$가 $10^9+7$로 나누어떨어지는 $[0, 10^9+7)$ 범위의 정수 $x$를 출력한다.

첫 줄에 $N$과 $K$가 주어진다. 다음 $N$개의 줄에는 각각 길이 $K$의 이진 표현이 나타내는 정수 $i \in (0, 2^K)$가 주어진다.

각 소에 대해 합을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

소에 할당된 비트열은 01, 01, 10, 11이다. 첫 번째 소의 합은 $\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}$이다. 두 번째 소의 비트열은 첫 번째 소와 같으므로 합도 같다. 세 번째 소의 합은 $\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}$이다.