Công ty A muốn tạo một bộ mã khóa, họ sử dụng \(N\) số ngẫu nhiên làm cơ sở sau đó dùng mô hình như sau để tạo các số tiếp theo:

\(F_k = (C_1\times F_{k-1} + C_2\times F_{k-2}+\cdots+C_n\times F_{k-n})\mod 10^9+7\)

Trong đó, \(F_0,F_1,...,F_{n-1}\) là cơ sở ban đầu, \(C_1,C_1,...,C_n\) là các hằng số cho trước.

Trong quá trình bảo trì hệ thống, vì hệ thống gặp lỗi nên công ty đã làm mất đi tài liệu lưu lại cơ sở ban đầu của mã khóa. Nhưng may mắn công ty vẫn lưu lại được một đoạn mã khóa liên tiếp độ dài \(N\) từ \(F_{k-n+1}\) đến \(F_k\).

Công ty muốn phục hồi lại dãy cơ sở, vì vậy họ thuê bạn đến đây. Nhiệm vụ của bạn là tìm lại dãy cơ sở từ dãy \(C\) và dãy \(F\) còn lại.

INPUT

Dòng đầu chứa 2 số nguyên \(n,k (0<n \leq50,1\leq k\leq10^9,0\leq k-n+1)\).

Dòng 2 chứa \(n\) số nguyên theo thứ tự \(F_k,F_{k-1},...,F_{k-n+1} (0\leq F_i\leq10^9) \)

Dòng 3 chứa \(n\) số nguyên theo thứ tự \(C_1,C_2,...,C_n(0<C_i\leq10^9)\).

OUTPUT

Gồm một dòng, in ra \(n\) số nguyên không âm theo thứ tự \(F_{n-1},...,F_1,F_0\) đã module \(10^9+7\)