#include <stdio.h>
#include <stdlib.h>
long long phi(long long n)
{
    long long rez;
    rez=n;
    for(long long i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            while(n%i==0) n=n/i;
            rez=rez-rez/i;
        }
    }
    if(n>1) 
    {
        rez=rez-rez/n;
    }
    return rez;
}
long long N;
long long exp_log_rec(long long x, long long n)
{
    //if(n < 0) return exp_log_rec(1.0 / x, -n);
    if(n == 0)  return 1;
    if(n % 2 == 0) return exp_log_rec(x*x%N, n/2)%N;
    if(n % 2 == 1) return (x * (exp_log_rec(x*x%N,n/2)%N))%N;
}
int main(void)
{
    FILE *f=NULL,*g=NULL;
    long long a,x;
    if((f=fopen("inversmodular.in","r"))==NULL)
    {
        perror(NULL);
        exit(-1);
    }
    if((g=fopen("inversmodular.out","w"))==NULL)
    {
        perror(NULL);
        exit(-1);
    }
    fscanf(f,"%lld %lld",&a,&N);
    if(fclose(f)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    x=phi(N);
    fprintf(g,"%lld",exp_log_rec(a%N,x-1)%N);
     if(fclose(g)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    return 0;
}