Cờ điểm là một trò chơi trên hệ tọa độ \(Oxy\). Mỗi lượt người chơi chọn một điểm \((x, y)\) trên hệ tọa độ để cắm một cột cờ. Ta gọi sức chứa của điểm thứ \(i\) có toạ độ \((x_i, y_i)\) là số lượng điểm \((u, v)\) thoả mãn hai điều kiện sau.

• \(u < x_i\) và \(v < y_i\)
• Điểm \((u, v)\) được cắm cột cờ trước thời điểm mà điểm \((x_i, y_i)\) được cắm cờ.

Nam vận hành một phần mềm cho trò chơi tính toán sức chứa của các điểm cắm cột cờ như vậy. Để kiểm duyệt độ chính xác của phần mềm này, Nam sinh ra các điểm cắm cột cờ một cách ngẫu nhiên để kiểm thử phần mềm.

Gọi \(F(i)\) là sức chứa của điểm \(x_i, y_i\) tại một thời điểm nhất định. Nếu các điểm bạn có là \((x_{1}, y_{1}), (x_{2}, y_{2}), \ldots\) thì \(F(i)\) là số lượng vị trí \(j\) thoả mãn:

• \(j < i\)
• \(x_{j} < x_{i}\) và \(y_{j} < y_{i}\)

Nam sẽ sinh ra \(n\) điểm ngẫu nhiên theo cách sau:

• Bắt đầu với giá trị \(x_{1} = A, y_{1} = B\). Ngoài ra có thêm hai giá trị nguyên dương \(MOD\) và \(P\).
• Giá trị \(x_{i}, y_{i}\) được xây dựng:
  • \(x_{i} = (x_{i - 1} + F(i - 1) \times P + (i + A)^{A})\ \text{mod}\ MOD + 1\).
  • \(y_{i} = (y_{i - 1} + F(i - 1) \times P + (i + B)^{B})\ \text{mod}\ MOD + 1\).

Đặt: \(X = \sum_{i = 1}^{N} F(i)\)
Yêu cầu: Bạn hãy giúp Nam tính giá trị \(X\) để kiểm thử phần mềm.

Input

• Gồm một dòng duy nhất chứ 5 số nguyên \(N, A, B, P, MOD\) \((1 \leq N \leq 7 \cdot 10^{4}, 1 \leq A, B \leq MOD \leq 10^{9}, 1 \leq P \leq 10^{9})\)

Output

• Ghi ra một dòng duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(2\) (\(25\%\) số điểm): \(MOD \leq 10^{3}\).
• Subtask \(3\) (\(25\%\) số điểm): \(MOD \leq 10^{5}\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

7 2 3 5 10

5