#include <bits/stdc++.h>
using namespace std;
FILE *fin, *fout;
long long n,nn;
long long putere(long long nr, long long p){
    if(p<=1) return nr%n;
    if(p%2==1) return nr*putere(nr*nr%n, p/2)%n;
    return putere(nr*nr%n, p/2)%n;
}

int main()
{
    fin=fopen("inversmodular.in", "r");
    fout=fopen("inversmodular.out", "w");
    long long a,i,phi;
    fscanf(fin, "%lld %lld", &a, &n);
    for(i=2, phi=n, nn=n; i*i<=nn; i++){
        if(nn%i==0){
            phi/=i;
            phi*=(i-1);
            while(nn%i==0)
                nn/=i;
        }
    }
    if(nn==phi) phi--;
    fprintf(fout, "%lld", putere(a,phi-1));

    return 0;
}