求助，用C语言解决这个问题
A－Rudy的礼物Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Description
过几天Rudy要过生日了，于是Rudy的好G友(Google+好友~)CydorniaKnight穿越回HFUT，给Rudy带了份生日礼物，当然CydoriaKnight的礼物当然不是就那么轻易可以拿到的，礼物装在一个盒子里面，盒子上有把密码锁，同时盒子上有两个正整数n和p，保证p是素数并且n < p， 打开密码锁的密码是一个正整数m，m必须满足这么两个条件：
1.n * m = 1 (mod p)
2.m < p
现在就请HFUT ACMer们帮Rudy把这个问题解决了吧，当然p的值可能会非常大，所以小盆友们就不要尝试用蛮力方法了～
Input
输入数据有多行，每行有两个正整数n和p，p是素数，同时0 < n < p < 100000008。输出以文件终止符结束。
Output
输出占一行，每行有一个整数m，保证所有的结果都存在且仅存在唯一的m。
Sample Input
8 11
4 7
3 29
8 100000007
Sample Output
7
2
10
12500001
Hint
据说装在盒子里的礼物是个很有爱的XX娃娃～
