#include <stdio.h>
#include <stdlib.h>

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

long long putere(long long n, long long p, long long mod)
{
    long long sol = 1;
    n = n % mod;
    while(p>0)
    {
        if(p % 2 == 1)
        {
            sol = (sol * n) % mod;
        }
        n = (n*n) % mod;
        p = p / 2;
    }
    return sol;
}

int main(void)
{
    long long a, n, sol, p;
    FILE *fin;
    FILE *fout;
        
    if((fin = fopen("inversmodular.in","r"))==NULL)
    {
        printf("Eroare deschidere fisier\n");
        exit(-1);
    }
        
    if((fout = fopen("inversmodular.out","w"))==NULL)
    {
        printf("Eroare deschidere fisier\n");
        exit(-1);
    }
    
    fscanf(fin,"%lld %lld", &a, &n);
    p = phi(n) - 1;
    fprintf(fout,"%lld\n", putere(a, p, n));
            
    fclose(fin);
    fclose(fout);
    
    return 0;
}