#include <cstdio>
#include <cmath>

using namespace std;

int mod;

int phi(int n)
{
	int lim=(int)sqrt((double)n);
	int ans=n;
	for(int i=2;i<=lim;i++)
	{
		bool ok=false;
		while(n%i==0)
		{
			n/=i;
			ok=true;
		}
		if(ok)
		{
			ans/=i;
			ans*=(i-1);
			lim=(int)sqrt((double)n);
		}
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}
int lgput(int n, int p)
{
	long long x=n;
	long long power=1;
    for(unsigned int i=0;(1<<i)<=p;i++)
    {
        if(((1<<i)&p))
            power=(power*x)%mod;
        x=(x*x)%mod;
    }
    return power;
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a, n;
    scanf("%d%d", &a, &n);
    mod=n;
    n=phi(n)-1;
    printf("%d\n", lgput(a, n));
    return 0;
}