#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 = 1; i <= p; i <<= 1 ) {

        if( i & p )
            XXX = (XXX*aux) % N;
        aux = (aux*aux) % N;
    }

    printf( "%lld", XXX );

    return 0;
}