לכל אחת מ־$N$ ($1\le N\le 5\cdot 10^5$) הפרות של Farmer John מוקצית מחרוזת סיביות באורך $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

Note

הפרות משויכות למחרוזות הסיביות הבאות: $[\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\}$.