#include<stdio.h>
#define N 2000000000

int descompun(int x)
{
	int i=2,calcul=x;
	while (i*i<=x)
	{
		int ok=0;
		while (x%i==0) {
			x/=i;
			ok=1;
		}
		if (ok)
			calcul=calcul/i*(i-1);
		++i;
	}
	if(x!=1)
		calcul=calcul/x*(x-1);
	return calcul;
}
int putere(int a,int p,int n)
{
	if (p==0) return 1;
	if (p%2) return (long long)a*putere((long long)a*a%n,p/2,n)%n;
	return putere((long long)a*a%n,p/2,n)%n;
}
int main()
{
	int a,n;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&a,&n);
	printf("%d\n",putere(a,descompun(n)-1,n));
	return 0;
}