Chacune des $N$ ($1\le N\le 5\cdot 10^5$) vaches de Farmer John se voit attribuer une chaîne de bits de longueur $K$ qui n'est pas entièrement composée de zéros ($1\le K\le 20$). Des vaches différentes peuvent se voir attribuer la même chaîne de bits.

La similarité de Jaccard de deux chaînes de bits est définie comme le nombre de bits à un dans leur intersection bit à bit divisé par le nombre de bits à un dans leur union bit à bit. Par exemple, la similarité de Jaccard des chaînes de bits $\texttt{11001}$ et $\texttt{11010}$ serait $2/4$.

Pour chaque vache, affichez la somme des similarités de Jaccard entre sa chaîne de bits et les chaînes de bits de chacune des $N$ vaches, y compris la sienne, modulo $10^9+7$. Plus précisément, si la somme est égale à un nombre rationnel $a/b$, où $a$ et $b$ sont des entiers sans facteur commun, affichez l'unique entier $x$ dans l'intervalle $[0,10^9+7)$ tel que $bx-a$ soit divisible par $10^9+7$.

Entrée

La première ligne contient $N$ et $K$. Chacune des $N$ lignes suivantes contient un entier $i\in (0,2^K)$, représentant une vache associée à la représentation binaire de $i$ sur $K$ bits.

Sortie

Affichez la somme modulo $10^9+7$ pour chaque vache sur une ligne distincte.

Exemples

Entrée 1

4 2
1
1
2
3

Sortie 1

500000006
500000006
500000005
500000006

Remarque

Les vaches sont associées aux chaînes de bits suivantes : $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Pour la première vache, la somme est $\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 chaîne de bits de la deuxième vache est la même que celle de la première, donc sa somme est la même que ci-dessus. Pour la troisième vache, la somme est $\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}$.

Pour la première vache, la somme est $\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}$. Pour la troisième vache, la somme est $\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 chaîne de bits de la deuxième vache est la même que celle de la première, donc sa somme est la même que ci-dessus. Pour la troisième vache, la somme est $\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}$.

Pour la troisième vache, la somme est $\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}$.

Contraintes

Entrées 2-15 : il y aura deux cas de test pour chacune des valeurs $K\in \{10,15,16,17,18,19,20\}$.