#include<fstream>
#define int1 long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int1 N, A, i = 2, j,  x, y,aux, v[1000], Nr;
int1 rid (int1 A, int1 fi)
{
    if(fi == 1)
        return A %N;
    if(fi % 2 == 0 )
    {
        int1 t = rid(A, fi/2 )%N;
        return (t *t) % N;
    }
    return rid(A, fi -1 )%N * A %N;



}
void read()
{
    int1 semn = -1, s =0 , fi = 0;
    fin >> A>> N;
    aux = N;
    while(aux > 1)
    {
        if(aux % i == 0)
        {
            v[++Nr] = i;
            while(aux % i == 0)

                aux /= i;


        }
        i++;

    }
    // for ( i = 1 ; i <= Nr ; i ++)
     //   fout << v[i] <<"  ";
    for ( i = 1 ; i <  1<<Nr; i++)
    {
        semn = -1;
        s = 0 ;
        for( j = 0 ; j < Nr; j++)
        {
            if( (1 << j )& i)
            {
               // fout << N <<" ";
                semn *= -1;
                s += N/ v[ j + 1 ];

            }
        }
       // fout << s <<" " ;

        fi += semn * s;
    }
    fi = N -fi -1 ;


    fout << rid(A, fi )% N;
}
int main()
{
    read();
    fin.close();
    fout.close();

    return 0;
}