#include <stdio.h>
int euler(int n)
{
	int i=1,rez=n; 
	for (i=2; i*i<=n; i++)
	{
		if (n%i==0)
		{
			while(n%i==0)
				n/=i;
			rez=rez/i*(i-1);
		}
	}
	if (n!=1)
		rez=rez/n*(n-1);
	return rez;
}
long long power(int a,int b,int c)
{
	long long s=1;
	while(b)  
    { 
		if (b%2)
			s=s*a%c;
		a=(long long)a*a%c;  
		b/=2;  
	}  
	return s;
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	int a,b,t;
	long long rez;
	scanf("%d%d",&a,&b);
	t=euler(b)-1;
	rez=power(a,t,b)%b;
	printf("%lld",rez);
	return 0;
}