A ciascuna delle $N$ ($1\le N\le 5\cdot 10^5$) mucche di Farmer John viene assegnata una stringa di bit di lunghezza $K$ che non è composta interamente da zeri ($1\le K\le 20$). A mucche diverse può essere assegnata la stessa stringa di bit.
La similarità di Jaccard di due stringhe di bit è definita come il numero di bit impostati a uno nella loro intersezione bit a bit diviso per il numero di bit impostati a uno nella loro unione bit a bit. Per esempio, la similarità di Jaccard delle stringhe di bit $\texttt{11001}$ e $\texttt{11010}$ è $2/4$.
Per ciascuna mucca, stampa la somma delle similarità di Jaccard della sua stringa di bit con le stringhe di bit di tutte le $N$ mucche, inclusa la propria, modulo $10^9+7$. Precisamente, se la somma è uguale a un numero razionale $a/b$, dove $a$ e $b$ sono interi senza fattori comuni, stampa l'unico intero $x$ nell'intervallo $[0,10^9+7)$ tale che $bx-a$ sia divisibile per $10^9+7$.
Formato dell'input
La prima riga contiene $N$ e $K$. Ognuna delle successive $N$ righe contiene un intero $i\in (0,2^K)$, che rappresenta una mucca associata alla rappresentazione binaria di $i$ di lunghezza $K$.
Formato dell'output
Stampa la somma modulo $10^9+7$ per ciascuna mucca su una riga separata.
Esempi
Input 1
4 2 1 1 2 3
Output 1
500000006 500000006 500000005 500000006
Note
Le mucche sono associate alle seguenti stringhe di bit: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Per la prima mucca, la somma è $\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}$. La stringa di bit della seconda mucca è uguale a quella della prima, quindi la sua somma è la stessa indicata sopra. Per la terza mucca, la somma è $\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}$.
Per la prima mucca, la somma è $\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}$. Per la terza mucca, la somma è $\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}$.
La stringa di bit della seconda mucca è uguale a quella della prima, quindi la sua somma è la stessa indicata sopra. Per la terza mucca, la somma è $\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}$.
Per la terza mucca, la somma è $\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}$.
Vincoli
Input 2–15: ci saranno due casi di test per ciascun $K\in \{10,15,16,17,18,19,20\}$.