Tìm căn bậc hai modulo của \(n\) theo \(p\), biết \(p\) là số nguyên tố lẻ thỏa \(p \equiv 3 \pmod{4}\). Công thức: \(x \equiv n^{\frac{p+1}{4}} \pmod{p}\). Đảm bảo tồn tại nghiệm.

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

• Một dòng chứa hai số nguyên \(n, p\) (\(0 \le n < p \le 10^9\), \(p\) nguyên tố, \(p \equiv 3 \pmod{4}\)).

Định dạng đầu ra

• Một số nguyên là căn bậc hai modulo, nằm trong \([0, p-1]\).

Ví dụ

Input:

2 7

Output:

4

Giải thích: \(4^2 = 16 \equiv 2 \pmod{7}\).

Ràng buộc

• 100% số điểm: \(p \le 10^9\).