It works … on my machine 😈

Cho bốn số nguyên ~n, x, y, m~. Dãy số ~A~ có độ dài ~n~ được tạo ra theo cách sau:

• ~a_1 = x~;
• ~a_i = (a_{i-1}*x+y) \% m~ với ~2 \le i \le n~.

Dãy số ~B~ là dãy số ~A~ sau khi sắp xếp không giảm.

Tính: ~\sum_{i=1}^{n} (b_i * i) \% m~

Input:

• Gồm một dòng chứa bốn số nguyên ~n, x, y, m~ ~(1 \le x, y \le m)~.

Output:

• In ra một số nguyên là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(40\%)~: ~n \le 10^5; m \le 10^9~;
• Subtask ~2~ ~(40\%)~: ~n \le 3*10^7; m \le 3*10^7~;
• Subtask ~3~ ~(20\%)~: ~n \le 10^{18}; m \le 10^6~;

Sample Input

3 2 1 10

Sample Output

0

Note

• Dãy số ~A~: ~2, 5, 1~;
• Dãy số ~B~: ~1, 2, 5~;
• Kết quả: ~(1*1+2*2+5*3)\%10=0~.