Lưu ý: Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi mức mặc định.

Mỗi cô trong số \(N\) cô bò của Farmer John (\(1\leq N\leq 5\cdot 10^5\)) được gán một xâu bit độ dài \(K\) không chứa toàn bit \(0\) (\(1\leq K\leq 20\)). Các cô bò khác nhau có thể được gán cùng một xâu bit.

Độ tương đồng Jaccard của hai xâu bit được định nghĩa là số bit \(1\) trong phép giao theo bit của chúng chia cho số bit \(1\) trong phép hợp theo bit của chúng. Ví dụ, độ tương đồng Jaccard của hai xâu bit \(\texttt{11001}\) và \(\texttt{11010}\) là \(2/4\).

Với mỗi cô bò, hãy in tổng độ tương đồng Jaccard giữa xâu bit của cô ấy với xâu bit của từng cô trong số \(N\) cô bò, kể cả chính cô ấy, theo modulo \(10^9+7\). Cụ thể, nếu tổng bằng số hữu tỉ \(a/b\), trong đó \(a\) và \(b\) là các số nguyên không có ước chung, hãy in số nguyên duy nhất \(x\) thuộc \([0,10^9+7)\) sao cho \(bx-a\) chia hết cho \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(N\) và \(K\).

\(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(i\in(0,2^K)\), biểu diễn một cô bò được gắn với dạng biểu diễn nhị phân độ dài \(K\) của \(i\).

Dữ liệu ra

Với mỗi cô bò, in tổng theo modulo \(10^9+7\) trên một dòng riêng.

Phân nhóm

• Các test 2–15: Có hai bộ test cho mỗi giá trị \(K\in\{10,15,16,17,18,19,20\}\).

Ví dụ

4 2
1
1
2
3

500000006
500000006
500000005
500000006

Nguồn

Đề bài gốc: USACO 2024 December Contest, Platinum — All Pairs Similarity

Tác giả: Benjamin Qi.