Każdej z $N$ ($1\le N\le 5\cdot 10^5$) krów Farmer John przypisano ciąg bitów długości $K$, który nie składa się wyłącznie z zer ($1\le K\le 20$). Różnym krowom można przypisać ten sam ciąg bitów.

Podobieństwo Jaccarda dwóch ciągów bitów definiuje się jako liczbę ustawionych bitów w ich bitowym przecięciu podzieloną przez liczbę ustawionych bitów w ich bitowej sumie. Na przykład podobieństwo Jaccarda ciągów $\texttt{11001}$ i $\texttt{11010}$ wynosi $2/4$.

Dla każdej krowy wypisz sumę podobieństw Jaccarda jej ciągu bitów do ciągów bitów wszystkich $N$ krów, łącznie z nią samą, modulo $10^9+7$. Dokładniej, jeśli suma jest równa liczbie wymiernej $a/b$, gdzie $a$ i $b$ są liczbami całkowitymi niemającymi wspólnych czynników, wypisz jedyną liczbę całkowitą $x$ z przedziału $[0,10^9+7)$, dla której $bx-a$ jest podzielne przez $10^9+7$.

Wejście

Pierwszy wiersz zawiera $N$ i $K$. Każdy z kolejnych $N$ wierszy zawiera liczbę całkowitą $i\in (0,2^K)$, reprezentującą krowę powiązaną z binarnym zapisem $i$ o długości $K$.

Wyjście

Dla każdej krowy wypisz sumę modulo $10^9+7$ w osobnym wierszu.

Przykład

Wejście 1

4 2
1
1
2
3

Wyjście 1

500000006
500000006
500000005
500000006

Uwagi

Krowom przypisano następujące ciągi bitów: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. Dla pierwszej krowy suma wynosi $\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}$. Ciąg bitów drugiej krowy jest taki sam jak ciąg pierwszej krowy, więc jej suma jest taka sama jak powyżej. Dla trzeciej krowy suma wynosi $\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}$.

Dla pierwszej krowy suma wynosi $\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}$. Dla trzeciej krowy suma wynosi $\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}$.

Ciąg bitów drugiej krowy jest taki sam jak ciąg pierwszej krowy, więc jej suma jest taka sama jak powyżej. Dla trzeciej krowy suma wynosi $\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}$.

Dla trzeciej krowy suma wynosi $\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}$.

Ograniczenia

Pliki wejściowe 2–15: Dla każdego $K\in \{10,15,16,17,18,19,20\}$ będą dwa przypadki testowe.