Нехай задані числа \(A\),\(N\). Зворотній елемент до числа \(A\) в кільці по модулю \(N\) називається таке число \(B\) що \((A \cdot B) \% N = 1\) , тобто остача від ділення \(A \cdot B\) на \(N\) дорівнює 1.

Формат вхідних даних

Два числа \(A,N\) (\(1 \le A,N \le 10^9\))

Формат вихідних даних

Виведіть значення зворотнього елементу до числа \(A\) за модулем \(N\). Якщо зворотнього елемента не існує - виведіть 0

Приклад вхідних даних

1 2

Приклад вихідних даних

1