#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,y=x;
    for(i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            while(x%i==0)
            {
                x/=i;
                y/=i;
                y*=(i-1);
            }
        }
    }
    if(x!=1) y=y/x*(x-1);
    return y;
}

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;
}