Mỗi con trong số $N$ ($1\le N\le 5\cdot 10^5$) con bò của Farmer John được gán một chuỗi bit có độ dài $K$ không gồm toàn bit không ($1\le K\le 20$). Các con bò khác nhau có thể được gán cùng một chuỗi bit.
Độ tương đồng Jaccard của hai chuỗi bit được định nghĩa là số bit bằng một trong phép giao theo bit của chúng chia cho số bit bằng một trong phép hợp theo bit của chúng. Ví dụ, độ tương đồng Jaccard của các chuỗi bit $\texttt{11001}$ và $\texttt{11010}$ là $2/4$.
Với mỗi con bò, hãy xuất tổng độ tương đồng Jaccard giữa chuỗi bit của nó và chuỗi bit của từng con trong $N$ con bò, bao gồm cả chính nó, lấy phần dư modulo $10^9+7$. Cụ thể, nếu tổng bằng một số hữu tỉ $a/b$, trong đó $a$ và $b$ là các số nguyên nguyên tố cùng nhau, hãy xuất số nguyên duy nhất $x$ trong khoảng $[0,10^9+7)$ sao cho $bx-a$ chia hết cho $10^9+7$.
Dữ liệu vào
Dòng đầu tiên chứa $N$ và $K$. Mỗi dòng trong $N$ dòng tiếp theo chứa một số nguyên $i\in (0,2^K)$, biểu diễn một con bò được gán dạng biểu diễn nhị phân có độ dài $K$ của $i$.
Dữ liệu ra
Xuất tổng modulo $10^9+7$ cho mỗi con bò trên một dòng riêng.
Ví dụ
Dữ liệu vào 1
4 2 1 1 2 3
Dữ liệu ra 1
500000006 500000006 500000005 500000006
Ghi chú
Các con bò được gán các chuỗi bit sau: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Đối với con bò thứ nhất, tổng là $\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006\pmod{10^9+7}$. Chuỗi bit của con bò thứ hai giống chuỗi bit của con bò thứ nhất, nên tổng của nó cũng giống như trên. Đối với con bò thứ ba, tổng là $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.
Đối với con bò thứ nhất, tổng là $\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006\pmod{10^9+7}$. Đối với con bò thứ ba, tổng là $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.
Chuỗi bit của con bò thứ hai giống chuỗi bit của con bò thứ nhất, nên tổng của nó cũng giống như trên. Đối với con bò thứ ba, tổng là $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.
Đối với con bò thứ ba, tổng là $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}$.
Giới hạn
Các tệp dữ liệu vào 2–15: có hai bộ kiểm thử cho mỗi $K\in \{10,15,16,17,18,19,20\}$.