Cho số nguyên tố \(p\) và ba số \(a, b, c\). Tính: \(S = (a! + C_b^c) \bmod p\). Trong đó \(C_b^c\) tính bằng định lý Lucas.

Định dạng đầu vào

• Một dòng chứa bốn số nguyên \(a, b, c, p\) (\(0 \le a < p \le 10^5\), \(0 \le c \le b \le 10^{18}\), \(p\) nguyên tố).

Định dạng đầu ra

• Một số nguyên là \(S \bmod p\).

Ví dụ

Input:

5 10 3 7

Output:

2

Giải thích: \(5! \equiv 1 \pmod{7}\), \(C_{10}^3 = 120 \equiv 1 \pmod{7}\), \(1+1 = 2\).

Ràng buộc

• 100% số điểm: \(p \le 10^5\), \(b \le 10^{18}\).