题目描述

模逆元是模运算中的乘法逆元素，对于整数 a 和模数 m，若存在整数 b 满足：a * b≡ 1 mod m，则称 b 为 a 在模 m 下的逆元，记作 a^-1 模逆元存在条件：a 与 m 必须互质（即 gcd(a,m)=1）。现要求你编写程序使用快速幂算法计算模逆元。

输入格式

输入为两个正整数，底数a和模数m

输出格式

输出为底数a在模数m下的逆元

样例

输入样例 1

2 3

输出样例 1

2 在模 3 下的逆元是: 2

输入样例 2

2 4

输出样例 2

逆元不存在（可能原因：a和m不互质或m非质数）

输入样例 3

3 7

输出样例 3

3 在模 7 下的逆元是: 5