Farmer John 的 $N$（$1\le N\le 5\cdot 10^5$）頭乳牛各自被分配了一個長度為 $K$ 且不全為零的位元字串（$1\le K\le 20$）。不同乳牛可以被分配相同的位元字串。

兩個位元字串的 Jaccard 相似度定義為：它們逐位交集中的置位位元數，除以它們逐位聯集中的置位位元數。例如，位元字串 $\texttt{11001}$ 和 $\texttt{11010}$ 的 Jaccard 相似度為 $2/4$。

對每頭乳牛，輸出她的位元字串與全部 $N$ 頭乳牛的位元字串（包括她自己）的 Jaccard 相似度總和，對 $10^9+7$ 取模。具體而言，如果總和等於有理數 $a/b$，其中 $a$ 和 $b$ 是互質整數，請輸出範圍 $[0,10^9+7)$ 中唯一使 $bx-a$ 能被 $10^9+7$ 整除的整數 $x$。

輸入格式

第一行包含 $N$ 和 $K$。接下來 $N$ 行各包含一個整數 $i\in (0,2^K)$，表示一頭乳牛對應到 $i$ 的長度為 $K$ 的二進位表示。

輸出格式

對每頭乳牛，將總和對 $10^9+7$ 取模後各自輸出一行。

範例

輸入格式 1

4 2
1
1
2
3

輸出格式 1

500000006
500000006
500000005
500000006

說明

乳牛對應到下列位元字串：$[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$。對第一頭乳牛，總和為 $\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}$。第二頭乳牛的位元字串與第一頭相同，所以她的總和也與上述相同。對第三頭乳牛，總和為 $\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}$。

對第一頭乳牛，總和為 $\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}$。對第三頭乳牛，總和為 $\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}$。

第二頭乳牛的位元字串與第一頭相同，所以她的總和也與上述相同。對第三頭乳牛，總和為 $\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}$。

對第三頭乳牛，總和為 $\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}$。

資料範圍

輸入 2-15：對每個 $K\in \{10,15,16,17,18,19,20\}$，各有兩個測試案例。