#include <cstdio>

using namespace std;

FILE *in,*out;

long long phi(long long n)
{
    long long d = 2,c = n,nr = 1,flag = 0;
    while(d*d <= c)
    {
        if(c % d == 0)
        {
            while(c % d == 0)
                c /= d;
            nr = (n/d) * (d-1);
            flag = 1;
        }
        d ++ ;
    }
    if(c != 1)
    {
        nr = nr / c * (c-1);
    }
    if(flag == 0)
        nr = n-1;
    return nr;
}

long long exp(long long n ,int p,long long modulo)
{
    long long rez = 1;
   while(p != 0)
    {
        if(p % 2 == 1)
            rez = (rez*n) % modulo;
        n = (n*n) % modulo;
        p /= 2;
    }
    return rez;
}

int main()
{
    in = fopen("inversmodular.in","r");
    out = fopen("inversmodular.out","w");
    long long a,n;
    fscanf(in,"%lld %lld",&a,&n);
    long long f = phi(n);
    fprintf(out,"%lld",exp(a,f-1,n));
    return 0;
}