#include <cstdio>
using namespace std;

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

int div(int n){
    int p1=1, p2=n;
    for(int i=2; i*i<=n; ++i)
        if(n%i==0){
            p2/=i;
            p1*=(i-1);
            while(n%i==0) n/=i;
        }
    if(n!=1){
        p2/=n;
        p1*=(n-1);
    }
    return p1*p2;
}

int put(long long a, long long b, int c){
    int p=1;
    while(b!=0){
        if(b%2==1){
            p=(p*a)%c;
            --b;
        }
        a=(a*a)%c;
        b/=2;
    }
    return p;
}

int main()
{
    int n, a, ff, nr, x;
    fscanf(f, "%d%d", &a, &n);
    ff=div(n);
    x=put(a, ff-1, n);
    fprintf(g, "%d", x);
return 0;
}