//#include <algorithm>
//using namespace std;
//
//typedef long long int int_64;
//
//int_64 A, N, XXX;
//
//int_64 phi( int_64 N ) {
//
//    int_64 i, aux;
//
//    aux =  N;
//    for( i = 2; i*i <= N; ++i )
//        if( N % i == 0 ) {
//
//            aux = aux/i * (i-1);
//            while( N % i == 0 )
//                N /= i;
//        }
//    if( N > 1 )
//        aux = aux/N * (N-1);
//
//    return aux;
//}
//
//int main() {
//
//    freopen( "inversmodular.in", "r", stdin );
//    freopen( "inversmodular.out", "w", stdout );
//
//    int_64 i, p, aux;
//
//    scanf( "%lld %lld", &A, &N );
//
//    p = phi( N ) - 1;
//    XXX = 1;
//    aux = A;
//    for( i = 0; (1<<i) <= p; ++i ) {
//
//        if( (1<<i) & p )
//            XXX = (XXX*aux) % N;
//        aux = (aux*aux) % N;
//    }
//
//    printf( "%lld", XXX );
//
//    return 0;
//}

#include<stdio.h>
#define LL long long


LL N,M;

LL getphi(LL nr)
{
	LL cur = nr;
	for(LL i = 2;i * i <= nr; ++i)
	{
		if (nr % i == 0)
		{
			while(nr % i == 0)nr /= i;
			cur = (cur / i) * (i - 1);
		}
	}
        if (nr != 1) cur = cur / nr * (nr - 1);
	return cur;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld %lld\n",&N,&M);
        LL put = getphi(M) - 1;
	LL nr = N;
	LL crt = 1;
    for(LL p = 1;p <= put;p <<= 1)
    {
	 	if (p & put) crt = (crt * nr) % M;
	  	nr = (nr * nr) % M;
	}
	printf("%lld\n",crt);
	return 0;
}