Jeder der $N$ ($1\le N\le 5\cdot 10^5$) Kühe von Farmer John wird eine Bitfolge der Länge $K$ zugewiesen, die nicht ausschließlich aus Nullen besteht ($1\le K\le 20$). Verschiedenen Kühen kann dieselbe Bitfolge zugewiesen werden.

Die Jaccard-Ähnlichkeit zweier Bitfolgen ist definiert als die Anzahl der gesetzten Bits in ihrem bitweisen Schnitt, geteilt durch die Anzahl der gesetzten Bits in ihrer bitweisen Vereinigung. Beispielsweise beträgt die Jaccard-Ähnlichkeit der Bitfolgen $\texttt{11001}$ und $\texttt{11010}$ genau $2/4$.

Gib für jede Kuh die Summe der Jaccard-Ähnlichkeiten ihrer Bitfolge mit den Bitfolgen aller $N$ Kühe einschließlich ihrer eigenen aus, modulo $10^9+7$. Genauer gesagt: Ist die Summe eine rationale Zahl $a/b$, wobei $a$ und $b$ ganze Zahlen ohne gemeinsame Faktoren sind, gib die eindeutige ganze Zahl $x$ im Bereich $[0,10^9+7)$ aus, für die $bx-a$ durch $10^9+7$ teilbar ist.

Eingabe

Die erste Zeile enthält $N$ und $K$. Jede der nächsten $N$ Zeilen enthält eine ganze Zahl $i\in (0,2^K)$, die eine Kuh mit der binären Darstellung von $i$ der Länge $K$ repräsentiert.

Ausgabe

Gib die Summe modulo $10^9+7$ für jede Kuh in einer eigenen Zeile aus.

Beispiele

Eingabe 1

4 2
1
1
2
3

Ausgabe 1

500000006
500000006
500000005
500000006

Hinweis

Den Kühen sind die folgenden Bitfolgen zugeordnet: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Für die erste Kuh ist die Summe $\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}$. Die Bitfolge der zweiten Kuh ist dieselbe wie die der ersten, daher ist ihre Summe dieselbe wie oben. Für die dritte Kuh ist die Summe $\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}$.

Für die erste Kuh ist die Summe $\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}$. Für die dritte Kuh ist die Summe $\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}$.

Die Bitfolge der zweiten Kuh ist dieselbe wie die der ersten, daher ist ihre Summe dieselbe wie oben. Für die dritte Kuh ist die Summe $\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}$.

Für die dritte Kuh ist die Summe $\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}$.

Beschränkungen

Eingaben 2–15: Für jedes $K\in \{10,15,16,17,18,19,20\}$ gibt es zwei Testfälle.