Cho hai số \(a\) và \(M\) (\(M\) là số nguyên tố). Hãy tìm số \(x\) (\(0 < x < M\)) sao cho \(a \times x \equiv 1 \pmod{M}\).

Nói cách khác, \(x\) là nghịch đảo modulo của \(a\) theo modulo \(M\).

Gợi ý: Sử dụng Định lý Fermat nhỏ: \(a^{M-2} \equiv a^{-1} \pmod{M}\) khi \(M\) nguyên tố và \(a \not\equiv 0 \pmod{M}\). Kết hợp với luỹ thừa nhanh (fast exponentiation).

Input

Một dòng chứa hai số \(a\) và \(M\) (\(2 \le M \le 10^9\), \(M\) nguyên tố, \(1 \le a < M\)).

Output

In ra \(x\) — nghịch đảo modulo của \(a\) theo \(M\).

Example

3 7

Output:

5

Giải thích: \(3 \times 5 = 15 \equiv 1 \pmod{7}\).