Hằng năm cứ vào khoảng cuối tháng 10, hai trường 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.

Input

• Dòng đầu chứa số ~N~, ~k~, ~T~, ~BASE~ trong đó ~N \le 10^{7}~, ~k \le 50~, ~T \le 10^{5}~, ~BASE \le 10^{12}~.

• Dòng tiếp theo chứa ~2~ số nguyên dương là ~mul~ và ~seed~.

• Lưu ý: ~30\%~ số test ~T \le 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} = (seed \times mul + seed) \bmod maxC~
  • ~A_{i} = (A_{i-1} \times mul + seed) \bmod maxC~
  • ~a \bmod b~ là phép lấy phần dư của phép chia ~a~ cho ~b~
  • ~0 \le mul, seed \le 10^{6}~
  • ~maxC = 2 ^ {20}~

Output

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

Sample Input

4 2 2 89133
3 6

Sample Output

50886