#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;
    vector<bool> viz(A);
    if(!(N%2))
    {
        while(!(N%2) && N)
            N/=2;
        totn=totn-totn/2;
    }
    for(i=3;i<=N;i+=2)
    {
        if(!viz[i])
        {
            if(!(N%i))
            {
                while(!(N%i) && N>1)
                    N/=i;
                totn=totn-totn/i;
            }
            for(j=i<<1;j<=N;j+=i)
                viz[j]=true;
        }
    }

    fprintf(out,"%d",putere(A,totn-1));




    return 0;
}