#include <cstdio>
using namespace std;

FILE *f=fopen ("inversmodular.in","r");
FILE *g=fopen ("inversmodular.out","w");

long long phi(int n){
    long long p=n;
    for (long long d=2;d*d<=n;++d){
        if (n%d==0){
            p=p*(d-1)/d;
            while (n%d==0) n/=d;

        }
    }
    if (n!=1) p=p*(n-1)*n;
    return p;
}

int main(){
    int n,k;
    long long a=0,p=1;

    fscanf (f,"%lld%d",&a,&n);
    k=phi(n)-1;

    while (k>0){
        if (k%2==1){
            p=((p%n)*(a%n))%n;
            k--;
        }
        a=((a%n)*(a%n))%n;
        k/=2;
    }

    fprintf (g,"%lld",p);

    return 0;
}