Chuẩn bị cho việc nghỉ hưu, giáo sư ~\mathrm{X}~ thử trải nghiệm cuộc sống mới bằng việc bắt tay vào trồng lúa. Các thửa ruộng của giáo sư có thể xem như chúng trải dài trên trục tọa độ từ 1 đến ~n~. Hiện đang sắp vào mùa hạn hán nên ông quyết định lắp đặt hệ thống tưới nước. Ông cho lắp ~n~ cái máy cấp nước, máy thứ ~i~ lắp tại điểm ~i~ có công suất là ~a_{i}~. Mỗi ngày máy thứ ~i~ sẽ bơm nước tới tất cả các điểm có tọa độ lớn hơn ~i~ để dự trữ nước, mỗi điểm sẽ nhận được một lượng nước bằng ~a_{i}~. Để chạy thử nghiệm, mỗi ngày Giáo sư điều chỉnh lại công suất của các máy, cụ thể máy ở điểm ~i~ sẽ được tăng thêm lượng nước bằng đúng tổng lượng nước mà điểm ~i~ nhận được của ngày hôm trước. Để đảm bảo cho hiệu quả của việc trồng lúa, giáo sư ~\mathrm{X}~ muốn biết sau ~m~ ngày thì công suất mỗi máy là bao nhiêu?

Dữ liệu:

• Dòng đầu là 1 số nguyên ~n(1 \leq n \leq 3000)~ là số máy bơm trên các thửa ruộng của Giáo sư;

• Dòng tiếp theo gồm ~n~ số nguyên ~a_{i} \left(1 \leq a_{i} \leq 10^{9}\right)~ là lượng nước máy thứ ~i~ tưới mỗi ngày cho các điểm tiếp theo;

• Dòng cuối là số nguyên ~m\left(1 \leq m \leq 10^{9}\right)~ số ngày tưới nước.

Kết quả:

• Ghi ra một dòng duy nhất gồm ~n~ số nguyên là công suất mỗi máy sau ~m~ ngày. Vì kết quả rất lớn nên bạn chỉ cần in ra phần dư của đáp số sau khi chia cho ~10^{9}+7~.

Ví dụ:

Sample Input

5 
4 2 8 1 1 
2

Sample Output

4 10 24 39 55

Giải thích:

Công suất 5 máy qua mỗi ngày: Ngày 1: 4 6 14 15 16. Ngày 2: 4 10 24 39 55.

Ràng buộc:

• Subtask 1: Có ~30 \%~ số test có ~n \times m \leq 10^{6}~;

• Subtask 2: Có ~30 \%~ số test có ~m \leq 10^{6}~;

• Subtask 3: Số test còn lại không có ràng buộc gì thêm.