#include <iostream>
#include <fstream>

using namespace std;

long long N, M, phi;

void gen( long long N )
{
    long long NN = N;

    phi = NN;

    for ( long long i = 2; i * i <= NN; ++i )
    {
        if ( NN % i ) continue;

        while ( NN % i == 0 ) NN /= i;

        phi = ( phi / i ) * ( i - 1 );
    }

    if ( NN > 1 )
    {
        phi = ( phi / NN ) * ( NN - 1 );
    }
}

long long pw( long long a, long long p, long long M )
{
    long long res = 1;

    for ( long long i = 0; ( 1LL << i ) <= p; ++i )
    {
        if ( p & ( 1LL << i ) )
                res = ( res * a ) % M;

        a = ( a * a ) % M;
    }

    return res;
}

int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodulor.out");

    f >> N >> M;

    gen( M );

    g << pw( N, phi - 1, M );

    return 0;
}