Uzumaki algorit nổi tiếng là \(1\) ninja nổi tiếng có rất nhiều nhẫn thuật mạnh, không chỉ thế anh còn sở hữu tuyệt kĩ thông não chi thuật mà cho dù kẻ thù mạnh đến thế nào cũng sẽ bị tẩy não. Trận chiến với Madara lần này cũng không phải ngoại lệ, sau khi đã ăn \(1\) rổ hành từ Madara không còn cách nào khác algorit đành phải dùng chiêu thông não chi thuật của mình. Tiếc thay lần này Madara lại là \(1\) kẻ địch rất cứng rắn nên dù có thuyết phục hay tẩy não thế nào cũng không có tác dụng. Trong lúc tưởng chừng như chẳng còn hi vọng nào thì bỗng ông bụt hiện ra, bụt nói nếu algorit giải được bài toán này thì có thể thông não Madara.

Bài toán là Cho dãy số nguyên gôm n phần tử , \(A_1 , A_2 , ... , A_n\).

Chúng ta có thể biến đổi \(k\) lần , với các lần biến đổi là chọn một phần tử của mảng đó tăng lên \(x\) đơn vị hoặc giảm đi \(x\) đơn vị . Hãy biến đổi tối ưu sao cho tích của mảng đạt kết quả lớn nhất .

algorit vì mãi lo nghĩ cho thằng bạn của mình là *Uchiha *bin9638 nên đã quên hết kiến thức toán rồi. Hãy giúp algorit nhé !

Input:

• Dòng đầu tiên gồm \(3\) số nguyên dương \(n , k , x , mod . ( n \le 3*10^5 , k \le 3*10^5 , x \le 10^{12} , mod \le 10^{18}\))
• Dòng thứ hai là dãy số \(A_1 , A_2 , ... , A_n\) . (\(|A_i| \le 10^{12}\))

Output:

• Là một số nguyên duy nhất , là kết quả của bài toán , vì kết quả của bài toán rất lớn nên kết quả sẽ được lấy dư khi chia cho \(mod\).*

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, k, x, |A_i|\) \(\le 10^3\) , \(mod = 10^9 + 7.\)
• Subtask \(2\) (\(20\%\) số điểm): \(n\) và \(k \le 2.10^5 , |A_i|\) và \(x \le 10^9, mod = 10^9 + 7.\)
• Subtask \(3\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

5 1 3 101
2 2 2 2 2

80