Tìm nghịch đảo modulo: Cho hai số nguyên dương \(A\) và M nguyên tố cùng nhau. Tìm X nhỏ nhất (\(1 \le X < M\)) sao cho \(A \cdot X \equiv 1 \pmod M\).

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

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

Định dạng đầu ra

• In ra số nguyên \(X\). Nếu không tồn tại nghịch đảo modulo, in ra -1.

Ví dụ

Input:

3 11

Output:

4

Giải thích: \(3 \times 4 = 12 \equiv 1 \pmod{11}\).

Ràng buộc & Subtasks