#include<stdio.h>   
#define LL long long   
  
  
LL N,M;   
  
LL cauta(LL nr)   
{   
    LL c=nr;   
    for(LL i=2;i * i <= nr; ++i)   
    {   
        if (nr % i == 0)   
        {   
            while(nr % i == 0)nr /= i;   
            c = (c / i) * (i - 1);   
        }   
    }   
        if (nr != 1) c = c / nr * (nr - 1);   
    return c;   
}   
  
int main()   
{   
    freopen("inversmodular.in","r",stdin);   
    freopen("inversmodular.out","w",stdout);   
    scanf("%lld %lld\n",&N,&M);   
        LL put =cauta(M) - 1;   
    LL nr = N;   
    LL crt = 1;   
    for(LL p = 1;p <= put;p<<=1)   
    {   
        if (p & put) crt = (crt * nr) % M;   
        nr = (nr * nr) % M;   
    }   
    printf("%lld\n",crt);   
    return 0;   
}