#include <cstdio>

using namespace std;

FILE *in,*out;

long long phi(int n)
{
    int cn = n,d = 2;
    long long r = n;
    while(d*d <= cn)
    {
        int flag = 0;
        while(cn % d == 0)
        {
            cn /= d;
            flag = 1;
        }
        if(flag == 1)
            r *= (n-(1/d));
        d ++;
    }
    if(cn > 1)
        r = n-1;
    return r;
}

int exp(long long n ,int p,int modulo)
{
    int 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 %d",&a,&n);
    long long f = phi(n);
    fprintf(out,"%d",exp(a,f-1,n));
    return 0;
}