#include <stdio.h>

unsigned long long expo(unsigned long long x, unsigned long long n)
{
    if(n<0)
        return expo(1.0/x, -n);
    if(n==0)
        return 1;
    if(n%2==0)
        return expo(x*x, n/2);
    if(n%2==1)
        return x*expo(x*x, n/2);
}

unsigned long long phi(unsigned long long n)
{
    unsigned long long rez=n;
    for(unsigned long long i=2; i*i<=n; ++i)
    {
        if(n%i==0)
        {
            while(n%i==0)
                n/=i;
            rez-=rez/i;
        }
    }
    if(n>1)
        rez-=rez/n;
    return rez;
}

int main()
{
    FILE *fin=fopen("inversmodular.in", "r");
    FILE *fout=fopen("inversmodular.out", "w");
    unsigned long long int A, N;
    fscanf(fin,"%lld %lld", &A, &N);
    fprintf(fout,"%lld", expo(A, phi(N)-1)%N);
}