Farmer John の $N$ 頭（$1\le N\le 5\cdot 10^5$）の牛には、それぞれすべてがゼロではない長さ $K$ のビット列（$1\le K\le 20$）が割り当てられています。異なる牛に同じビット列が割り当てられていてもかまいません。

2 つのビット列の Jaccard 類似度は、ビットごとの積集合で立っているビットの数を、ビットごとの和集合で立っているビットの数で割ったものと定義します。例えば、ビット列 $\texttt{11001}$ と $\texttt{11010}$ の Jaccard 類似度は $2/4$ です。

各牛について、その牛のビット列と、自分自身を含む $N$ 頭すべての牛のビット列それぞれとの Jaccard 類似度の和を、$10^9+7$ で割った余りとして出力してください。具体的には、その和が有理数 $a/b$ に等しく、整数 $a$ と $b$ が共通の因子を持たないとき、$bx-a$ が $10^9+7$ で割り切れるような範囲 $[0,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}$ です。2 番目の牛のビット列は最初の牛と同じなので、和も上と同じです。3 番目の牛について、和は $\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}$ です。3 番目の牛について、和は $\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 番目の牛のビット列は最初の牛と同じなので、和も上と同じです。3 番目の牛について、和は $\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}$ です。

3 番目の牛について、和は $\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\}$ について、2 つのテストケースがあります。