#include <stdio.h>

int expo(int x, int n)
{
    if(n == 0)
        return 1;
    int p = 1;
    while(n > 0)
    {
        if(n%2)
            p = p * x;

        x = x * x;
        n = n /2;
    }
    return p;
}

int phi(int n)
{
    int rez=n;
    for(int 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;
}

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