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

using namespace std;

int N,a,n,b=1;

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