Trong buổi học toán, cô giáo cho lớp bài toán: Tìm số nguyên \(x\) sao cho \(a \times x \equiv 1 \pmod{M}\). Em hãy giúp các bạn giải bài toán này. Dữ liệu đảm bảo tồn tại nghịch đảo.

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

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

Định dạng đầu ra

• Một số nguyên duy nhất là nghịch đảo modulo của \(a\) theo \(M\), nằm trong khoảng \([0, M-1]\).

Ví dụ

Input:

3 7

Output:

5

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

Ràng buộc

• 100% số điểm: \(1 \le a < M \le 10^9\), \(\gcd(a, M) = 1\).