Farmer John의 $N$ ($1\le N\le 5\cdot 10^5$)마리 소에는 각각 모든 비트가 0인 문자열이 아닌 길이 $K$의 비트 문자열이 배정되어 있다 ($1\le K\le 20$). 서로 다른 소에 같은 비트 문자열이 배정될 수도 있다.

두 비트 문자열의 Jaccard 유사도는 두 문자열의 비트별 교집합에서 1인 비트의 수를 비트별 합집합에서 1인 비트의 수로 나눈 값으로 정의된다. 예를 들어 비트 문자열 $\texttt{11001}$과 $\texttt{11010}$의 Jaccard 유사도는 $2/4$이다.

각 소에 대해, 자신의 비트 문자열과 자신을 포함한 $N$마리 소 각각의 비트 문자열 사이의 Jaccard 유사도를 모두 더한 값을 $10^9+7$로 나눈 나머지로 출력한다. 구체적으로, 합이 공약수가 없는 정수 $a$와 $b$로 이루어진 유리수 $a/b$라면, $bx-a$가 $10^9+7$로 나누어떨어지게 하는 $[0,10^9+7)$ 범위의 유일한 정수 $x$를 출력한다.

입력

첫 번째 줄에는 $N$과 $K$가 주어진다. 다음 $N$개의 줄에는 각각 정수 $i\in (0,2^K)$가 주어지며, 이는 $i$의 길이 $K$인 이진수 표현이 배정된 소를 나타낸다.

출력

각 소에 대해 합을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제

입력 1

4 2
1
1
2
3

출력 1

500000006
500000006
500000005
500000006

참고

소에 배정된 비트 문자열은 다음과 같다: $[\texttt{01}, \texttt{01}, \texttt{10}, \texttt{11}]$. 첫 번째 소의 합은 $\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}$이다. 두 번째 소의 비트 문자열은 첫 번째 소와 같으므로 합도 위와 같다. 세 번째 소의 합은 $\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}$이다.

첫 번째 소의 합은 $\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}$이다. 세 번째 소의 합은 $\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}$이다.

두 번째 소의 비트 문자열은 첫 번째 소와 같으므로 합도 위와 같다. 세 번째 소의 합은 $\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}$이다.

세 번째 소의 합은 $\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}$이다.

제한

입력 2-15: $K\in \{10,15,16,17,18,19,20\}$의 각 값에 대해 테스트 케이스가 두 개씩 있다.