#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout ("inversmodular.out");
int a,n,x,phi,i;

long long pw(int A , int N)
{
    if(N == 0)
        return 1;
    if(N % 2 == 1)
        return (A%n) * (pw(A , N - 1)%n);
    long long P = pw(A , N / 2)%n;
    return (P * P)%n;
}

long long Euler(long long numar)
{
	long long fi=numar;
	for (i=2;i<=sqrt(numar);i++)
	{
		if (numar%i==0)
		{
			while(numar%i==0)numar/=i;
			fi=(fi/i)*(i-1);
		}
	}
	if (numar!=1)fi=fi/numar*(numar-1);
	return fi;
}

int main()
{
	fin >> a >>n ;
	phi = Euler(n);
	x=pw(a,phi-1);
	fout << x%n << "\n";
	return 0;
}