Ở một đất nước nọ, có \(n\) người dân sống thành một vòng tròn, đánh số từ 0 đến \(n-1\) (\(n\) là một số lẻ). Hiện tại độ hạnh phúc của người thứ \(i\) là \(a_i\). Mỗi buổi sáng, họ sẽ gửi thiệp chúc mừng cho nhau. Buổi chiều khi tan làm, mọi người đều rất mệt mỏi và độ hạnh phúc trở về \(0\).

May mắn thay, lúc này họ nhận được thiệp chúc mừng từ bàn bè. Người càng hạnh phúc thì bức thiệp họ làm ra càng đẹp, do đó càng khiến người nhận thấy hạnh phúc. Độ hạnh phúc của một người vào cuối ngày (cũng là độ hạnh phúc vào buổi sang hôm sau) được tính bằng tổng độ hạnh phúc của những người đã gửi thiệp cho anh ta.

Vào ngày thứ 0, tất cả hàng xóm gửi thiệp cho nhau. Mỗi ngày họ đều tăng khoảng cách gửi lên gấp đôi so với ngày hôm trước. Cụ thể, vào ngày thứ \(i\), người thứ \(i\) gửi thiệp cho người thứ \((i + 2^i)\) \( modulo \) \(n \) và \((i- 2^i\) \( modulo \) \(n + n)\) \( modulo \) \(n\). Lưu ý là một người có thể gửi hai tấm thiệp cho cùng một người khác, cũng có thể gửi thiệp cho chính mình.

Yêu cầu: Hãy tính độ hạnh phúc của từng người sau \(k\) ngày.

Input

• Dòng đầu chứa hai số tự nhiên \(n, k\).

• Dòng tiếp theo chứa \(n\) số nguyên \(a_0,a_2,…,a_{n-1}\)

Output

Ghi \(n\) số là độ hạnh phúc của \(n\) người trên một dòng. Kết quả rất lớn, nên chỉ cần in ra phần dư khi chia kết quả cho \(10^9+7\).

Hạn chế

• \(0 ≤ n ≤ 10^6, 0 ≤ k ≤ 10^9\)

• Có 10% số test với \(k ≤ 100\).

• Có 30% số test với \(n ≤ 100\).

• Có 30% số test với \(a_i=1\).

• Có 30% số test với ràng buộc gốc.

Sample Input

3 1
1 2 3

Sample Output

5 4 3

Sample Input

3 2
1 2 3

Sample Output

7 8 9