Farmer John 的 $N$ ($1\le N\le 5\cdot 10^5$) 头奶牛每头都被分配了一个长度为 $K$ 且不全为零的位串（$1\le K\le 20$）。不同的奶牛可能会被分配到相同的位串。

两个位串的 Jaccard 相似度定义为它们按位与运算结果中置位（即 1）的个数除以它们按位或运算结果中置位的个数。例如，位串 $\texttt{11001}$ 和 $\texttt{11010}$ 的 Jaccard 相似度为 $2/4$。

对于每一头奶牛，输出她所持有的位串与所有 $N$ 头奶牛（包括她自己）的位串的 Jaccard 相似度之和，结果对 $10^9+7$ 取模。具体来说，如果和为一个有理数 $a/b$，其中 $a$ 和 $b$ 互质，则输出唯一的整数 $x \in [0, 10^9+7)$，使得 $bx-a$ 能被 $10^9+7$ 整除。

输入格式

第一行包含 $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}$。

数据范围

测试点 2-15：对于每个 $K\in \{10,15,16,17,18,19,20\}$，各有两组测试数据。