#include<stdio.h>
#include<vector>
#include<math.h>
FILE *in,*out;
using namespace std;
int N,A,totn=1,i,j,MOD;

int putere(int n,int p)
{
    int rez=1;
    for(i=0;(1<<i)<=p;i++)
    {
        if(((1<<i)& p))
            rez=(rez*n)%MOD;
        n=(n*n)%MOD;
    }
    return rez;
}

int main()
{
    in=fopen("inversmodular.in","rt");
    out=fopen("inversmodular.out","wt");
    fscanf(in,"%d %d",&A,&N);
    totn=N;
    MOD=N;
    bool ok=false;
    if(!(N%2))
    {
        while(!(N%2) && N)
            N/=2;
        ok=true;
        totn=totn-totn/2;
    }
    for(i=3;i<=N/2;i+=2)
    {
        if(!(N%i))
        {
            ok=true;
            while(!(N%i) && N>1)
                    N/=i;
            totn=totn-totn/i;
        }
    }
    if(!ok)
        totn--;
    fprintf(out,"%d",putere(A,totn-1));




    return 0;
}