描述 Description

有理数取余：给定m,p,q,求p/q(分数)对m取余的值其中m,p,q,为正整数

输入数据保证(m,q)=1

只需输出一行一个整数即可

输入格式 Input Format

一行三个整数m,p,q

输出格式 Output Format

一行一个正整数x,表示p/q mod m的余数

样例输入

输入样例1:

5 13 6

输入样例2:

4 5 7

样例输出

输出样例1:

3

输出样例2:

3

时间限制

每个测试点0.1s(均在我的程序本机测试时间4倍以上)

注释 Hint

对于10%的数据保证p,q,m<=10

对于50%的数据保证m为质数

对于100%的数据p,q<=10^50,m<=2x10^9