#include <fstream>
#include <stdint.h>
#include <math.h>
using namespace std;
fstream f1("inversmodular.in", ios::in);
fstream f2("inversmodular.out", ios::out);
int32_t a, n, phi;
uint64_t putere=1, temp;
int32_t p(int32_t n)
{
    ///p(n)= numar numere cuprinse intre 1 si n si prime cu n
    int32_t rez=n;
    int32_t put=0, div=2, sqrtn=sqrt(n);
    ///div factor prim
    while((n!=1)&&(div<=sqrtn))
    {
        while(n%div==0) {n/=div;put++;}

        if(put) rez= (rez/div) *(div -1); ///in loc de rez=rez*(1- 1/div) , rez divizibil cu div implicit

        div++;
        put=0;
    }
    if(n!=1)  rez= (rez/n) *(n-1);///nr este si el un factor prin la puterea 1
    return rez;
}
int main()
{
    int32_t i;
    f1>>a>>n;
    ///inversul modular este acel numar x<n a.i. (a*x)%n=1
    ///din teorema lui euler => x=a^(phi(n)-1) (% n) - %n nu afecteaza rezulatul final
    ///phi(n)=numarul numerelor <=n si prime cu n
    phi=p(n);
    phi--;

    temp=a;///temp= a^2^i
    for(i=0; (1<<i)<=phi; i++)
    {
        if((1<<i) & phi ) {putere*=temp ; putere%=n;}
        temp=(temp*temp)%n;
    }
   f2<<putere;
   return 0;
}