A cada una de las $N$ ($1\le N\le 5\cdot 10^5$) vacas de Farmer John se le asigna una cadena de bits de longitud $K$ que no está formada únicamente por ceros ($1\le K\le 20$). A distintas vacas se les puede asignar la misma cadena de bits.

La similitud de Jaccard de dos cadenas de bits se define como el número de bits a uno en su intersección bit a bit dividido por el número de bits a uno en su unión bit a bit. Por ejemplo, la similitud de Jaccard de las cadenas $\texttt{11001}$ y $\texttt{11010}$ sería $2/4$.

Para cada vaca, imprime la suma de las similitudes de Jaccard de su cadena de bits con las cadenas de cada una de las $N$ vacas, incluida la suya propia, módulo $10^9+7$. En concreto, si la suma es igual a un número racional $a/b$, donde $a$ y $b$ son enteros sin factores comunes, imprime el único entero $x$ del intervalo $[0,10^9+7)$ tal que $bx-a$ sea divisible por $10^9+7$.

Entrada

La primera línea contiene $N$ y $K$. Cada una de las siguientes $N$ líneas contiene un entero $i\in (0,2^K)$, que representa una vaca asociada a la representación binaria de $i$ de longitud $K$.

Salida

Imprime la suma módulo $10^9+7$ para cada vaca en una línea separada.

Ejemplos

Entrada 1

4 2
1
1
2
3

Salida 1

500000006
500000006
500000005
500000006

Nota

Las vacas están asociadas a las siguientes cadenas de bits: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Para la primera vaca, la suma es $\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 cadena de bits de la segunda vaca es igual a la de la primera, así que su suma es la misma que la anterior. Para la tercera vaca, la suma es $\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 la primera vaca, la suma es $\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 la tercera vaca, la suma es $\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 cadena de bits de la segunda vaca es igual a la de la primera, así que su suma es la misma que la anterior. Para la tercera vaca, la suma es $\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 la tercera vaca, la suma es $\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}$.

Restricciones

Archivos de entrada 2–15: habrá dos casos de prueba para cada $K\in \{10,15,16,17,18,19,20\}$.