#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int N,a,n,b=1;

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