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\}$ 中的每个值，都有两个测试用例。