Giải bài trực tuyến

Hằng năm cứ vào khoảng cuối tháng 10, hai trườnng trung học danh tiếng nhất ở nước Alphabet, trường XYZ và trường ABC, sẽ tổ chức giải bóng chuyền với mục đích tạo ra sân chơi lành mạnh giữa các học sinh của hai trường và cũng là dịp để các học sinh tìm hiểu kỹ hơn về trường bạn. Vì sân vận động rất lớn nên mỗi đội có tới N người chơi. Trường XYZ là một trường chuyên về các môn tự nhiên còn trường ABC là trường chuyên về các môn xã hội. Để chuẩn bị chiến thuật cho giải đấu sắp tới, trường XYZ cần phải biết mức độ bá đạo của đội bên kia. Nhờ quen biết rộng nên trường XYZ đã biết được  chỉ số trung bình các thí sinh sắp tới sẽ chơi cho đội của trường ABC. Độ bá đạo của của một đội bóng chuyền sẽ có giá trị bằng tổng độ bá đạo của các thành viên trong đội và lấy phần dư trong phép chia cho BASE trong đó độ bá đạo của mỗi thành viên sẽ bằng lũy thừa bậc Q của chỉ số trung bình của thành viên đó. Biết rằng Q có dạng là k^T.

Yêu cầu: Tính độ bá đạo của đội bóng trường ABC.

Dữ liệu vào

• Dòng đầu chứa số N, k, T, BASE trong đó N <= 10⁷, k <= 50, T <= 10⁵, BASE <= 10¹² .
• Dòng tiếp theo chứa 2 số nguyên dương là mul và seed.
• Lưu ý: 30% số test T <= 50. 
• Nguyên tắc sinh dãy A với A[i] là chỉ số trung bình của thành viến thứ i như sau:
  • A[1] = (mul*seed  + seed)  mod maxC.
  • A[i]  = (A[i-1]*mul + seed) mod maxC.
  • a mod b là phép lấy phần dư của phép chia a cho b.
  • 0 <= mul, seed <= 10⁶.
  • maxC = 2^20.

Dữ liệu ra

• Gồm một dòng chứa mốt số nguyên là kết quả bài toán.

Ví dụ

Dữ liệu vào: 

4 2 2 89133

 3 6

Dữ liệu ra: 

50886