#include <algorithm>
using namespace std;

typedef int int_32;
typedef long long int int_64;

int_32 A, N;
int_64 XXX;

int_32 phi( int_32 N ) {

    int_32 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_32 i, p;
    int_64 aux;

    scanf( "%d %d", &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;
}