#include <iostream>
#include <fstream>
#include <cmath>
#define ull unsigned long long

using namespace std;

ull N,a,n,b=1;

ull phi(ull x)
{
    ull i,j=x-1;
    for(i=2;i*i<=x;i++)
    {
        if(x%i==0)
           j-=(x/i),x/=i;
    }
    return j;
}
int main()
{
    ull i,j=1;
    FILE *f=fopen("inversmodular.in","r");
    FILE *g=fopen("inversmodular.out","w");
    fscanf(f,"%lld %lld",&a,&n);
    i=phi(n)-1;
    while(i)
    {
        if(i>>1<<1!=i)
            j=(j*a)%n;
        a*=a;
        a%=n;
        i/=2;
    }
    j%=n;
    fprintf(g,"%lld\n",j);
    return 0;
}