#include<stdio.h>
#include<math.h>

long long exp(long long n, long long p)
{
    // infoarena: Ridicare la putere in timp logaritmic
    // http://www.infoarena.ro/job_detail/145518?action=view-source
    long long sol;
    long long a;
    a = n;
    for (int i = 0; (1<<i) <= p; ++ i)  // Luam toti biti lui p la rand
    {
        if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie 
            sol= (sol * a);
            // NOTA: ce reprezinta n^(2^i) ?
            a=(a * a); // Inmultim a cu a ca sa obtinem n^(2^(i+1))
    }
    return sol;
}

int main()
{
    long long A,N;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out", "w", stdout);
    
    scanf("%lld", &A);
    scanf("%lld", &N);
    
    // pentru 60% din teste N este prim
    long long phi = N-1;
    printf("%lld", (long long)pow(A,N-2)%N);
    return 0;
}