#include <stdio.h>
#include <stdlib.h>
long long phi(long long n)
{
    long long rez;
    rez=n;
    for(int 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 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/2);
    if(n % 2 == 1) return (x * (exp_log_rec(x*x,n/2)));
}
int main(void)
{
    FILE *f=NULL,*g=NULL;
    long long a,n,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,x-1)%n);
     if(fclose(g)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    return 0;
}