Modular Inverse

Given two integers a and b, find the smallest positive integer solution x to the congruence equation:

\( a\, x \equiv 1 \pmod{b} \)

It is guaranteed that a solution exists.

inputFormat

The input consists of two integers a and b separated by a space.

outputFormat

Output the smallest positive integer x satisfying \( a\, x \equiv 1 \pmod{b} \).

sample

3 11

4