题目描述

给定$a,p$，求$a$在模$p$意义下的乘法逆元。

这里，$a$在模$p$意义下的乘法逆元是指$ax\equiv 1\pmod p$的解。

输入格式

输入一行两个正整数$a,p$。

输出格式

输出一行一个正整数，表示你的答案。如果不存在乘法逆元，输出-1。

样例输入 #1

10 13

样例输出 #1

4

说明/提示

有$1\leq a,p\leq 10^9$。