Có \(2^n\) gia đình cùng sống trong một khu phố, các gia đình được đánh số từ \(1\) đến \(2^n-1\). Sau mỗi ngày, mỗi gai đình đều gửi tặng cho tất cả các gia đình khác một số quả, số quả này tính dựa trên số quả gia đình đó nhận được ngày trước đó. Cụ thể, gọi \(f_i\) là tổng số quả gia đình \(i\) nhận được ngày \(d\) thì sang ngày tiếp theo \(d+1\), gia đình \(i\) sẽ gửi cho gia đình \(j\) (\(j \neq i\)) số quà là \(f_i \times (2 \times (i | j) - i - j)\), trong đó \(|\) là phép toán \(OR\).

Yêu cầu: Cho biết số gia đình trong khu phố và số quả mỗi gia đình được nhận ở ngày \(0\), tính số quả mỗi gia đình nhận được ở ngày \(k\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,k\) (\(n \le 20, k \le 10^9\)).
• Dòng thứ hai chứa \(2^n\) số nguyên không âm, số thứ \(i\) là số quả gia đình \(i\) nhận được ở ngày hiện tại. Các số không vượt quá \(10^9\).

Output

• Ghi ra \(n\) số nguyên trên một dòng, số thứ \(i\) là tổng số quả mà gia đình \(i\) nhận được vào ngày thứ \(k\), lấy phần dư khi chia cho (\(10^9+7\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10, k \le 5\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10, k \le 1000\).
• Subtask \(3\) (\(30\%\) số điểm): \(k \le 10^5\).
• Subtask \(4\) (\(10\%\) số điểm): không có ràng buộc gì thêm.

Example

2 1
3 4 5 1

17 20 19 22