Cada uma das $N$ ($1\le N\le 5\cdot 10^5$) vacas de Farmer John recebe uma cadeia de bits de comprimento $K$ que não é composta apenas de zeros ($1\le K\le 20$). Vacas diferentes podem receber a mesma cadeia de bits.

A similaridade de Jaccard entre duas cadeias de bits é definida como o número de bits iguais a um em sua interseção bit a bit dividido pelo número de bits iguais a um em sua união bit a bit. Por exemplo, a similaridade de Jaccard entre as cadeias $\texttt{11001}$ e $\texttt{11010}$ seria $2/4$.

Para cada vaca, imprima a soma das similaridades de Jaccard de sua cadeia com as cadeias de cada uma das $N$ vacas, incluindo ela própria, módulo $10^9+7$. Mais precisamente, se a soma for igual a um número racional $a/b$, em que $a$ e $b$ são inteiros sem fatores comuns, imprima o único inteiro $x$ no intervalo $[0,10^9+7)$ tal que $bx-a$ seja divisível por $10^9+7$.

Entrada

A primeira linha contém $N$ e $K$. Cada uma das próximas $N$ linhas contém um inteiro $i\in (0,2^K)$, representando uma vaca associada à representação binária de $i$ com comprimento $K$.

Saída

Imprima a soma módulo $10^9+7$ para cada vaca em uma linha separada.

Exemplos

Entrada 1

4 2
1
1
2
3

Saída 1

500000006
500000006
500000005
500000006

Explicação

As vacas estão associadas às seguintes cadeias de bits: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Para a primeira vaca, a soma é $\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}$. A cadeia da segunda vaca é igual à da primeira, portanto sua soma é a mesma acima. Para a terceira vaca, a soma é $\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}$.

Para a primeira vaca, a soma é $\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}$. Para a terceira vaca, a soma é $\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}$.

A cadeia da segunda vaca é igual à da primeira, portanto sua soma é a mesma acima. Para a terceira vaca, a soma é $\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}$.

Para a terceira vaca, a soma é $\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}$.

Restrições

Entradas 2–15: Haverá dois casos de teste para cada $K\in \{10,15,16,17,18,19,20\}$.