题目描述

题目译自 USACO 2024 December Contest, Platinum Problem 1. All Pairs Similarity

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

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

对于每头奶牛，输出她的位串与**每头奶牛（包括她自己）**的位串的 Jaccard 相似度之和，对 $10^9+7$ 取模。具体地说，如果总和等于一个有理数 $a/b$，其中 $a$ 和 $b$ 是互质的整数，则输出范围 $[0, 10^9+7)$ 内的唯一整数 $x$，使得 $bx - a$ 被 $10^9+7$ 整除。

输入格式

输入的第一行包含 $N$ 和 $K$。

以下 $N$ 行每行包含一个整数 $i \in (0, 2^K)$，表示一头奶牛分配到了 $i$ 的 $K$ 位二进制表示。

输出格式

对于每头奶牛输出一行，包含所求的总和，对 $10^9+7$ 取模。

样例

输入

4 2
1
1
2
3

输出

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 + \frac{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 + \frac{1}{2} \equiv 500000005 \pmod{10^9+7} ]

数据范围与提示

• 测试点 $2$-$15$：对于每一个 $K \in \{10,15,16,17,18,19,20\}$ 有两个测试点。