#include <iostream>
#include <fstream>
#define ll long long

using namespace std;

ifstream x("inversmodular.in");
ofstream y("inversmodular.out");

ll a,n;

int inv(int a, int n)
{
	int p=n-2,r=1;
	while(p)
	{
		if(p%2)
		{
			r=(1LL*r*a)%n;
		}
		a=(1LL*a*a)%n;
		p/=2;
	}
	return r;
}


int main()
{
    x>>a>>n;
    y<<inv(a,n);
    x.close();
    y.close();
    return 0;
}