#include <fstream>
#include <vector>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int fi_totientE(int n)
{
	int fi=0;
	for(int i=n;i>1;i--)
	{
		if(n%i!=0)
		{
			fi++;
		}
	}
	return fi;
}

int expMn(int b,int e,int m)
{
	if(e==0)
	{
		return 1;
	}
	else
	{
		int put=b%m;
		b%=m;
		for(int i=1;i<e;i++)
		{
			put*=b;
			put%=m;
		}
		return put;
	}
}

int main()
{
	int a,n;
	fin>>a>>n;
	vector <bool > vPrime(n+1,true);
	for(int i=2; i<=n; i++)
	{
		int a=i;
		if(vPrime[i])
		{
			while(a+i<=n)
			{
				vPrime[a+i]=false;
				a+=i;
			}
		}
	}
	if(vPrime[n])
	{
		fout<<expMn(a,n-2,n);
	}
	else
	{
		fout<<expMn(a,fi_totientE(n)-1,n);
	}
    return 0;
}