تُسنَد إلى كل بقرة من بقرات Farmer John البالغ عددها $N$ ($1\le N\le 5\cdot 10^5$) سلسلة بتات طولها $K$ لا تتكون كلها من أصفار ($1\le K\le 20$). قد تُسنَد سلسلة البتات نفسها إلى بقرات مختلفة.

يُعرَّف تشابه Jaccard بين سلسلتي بتات بأنه عدد البتات التي تساوي واحدًا في تقاطعهما على مستوى البتات مقسومًا على عدد البتات التي تساوي واحدًا في اتحادهما على مستوى البتات. مثلًا، تشابه Jaccard بين سلسلتي البتات $\texttt{11001}$ و$\texttt{11010}$ يساوي $2/4$.

لكل بقرة، أخرج مجموع تشابه Jaccard بين سلسلة بتاتها وسلسلة بتات كل واحدة من البقرات الـ$N$، بما فيها هي نفسها، بترديد $10^9+7$. تحديدًا، إذا كان المجموع يساوي العدد النسبي $a/b$، حيث $a$ و$b$ عددان صحيحان لا يشتركان في أي عامل مشترك، فأخرج العدد الصحيح الوحيد $x$ في المجال $[0,10^9+7)$ الذي يجعل $bx-a$ قابلًا للقسمة على $10^9+7$.

الإدخال

يحتوي السطر الأول على $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\}$.