#include <iostream>
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
int pow(long long int baza, long long int exp){
    int rasp=1;
while(exp>0){
    if(exp%2==1)
        rasp*=baza;
    baza*=baza;
    exp/=2;
}

return rasp;
}

int powmod(long long int baza, long long int exp, int mod){
    int rasp=1;
while(exp>0){
    if(exp%2==1)
        rasp=(rasp*baza)%mod;
    baza=(baza*baza)%mod;
    exp/=2;
}

return rasp;
}

int main() {
    FILE *fin, *fout;
    int i, lim, expo, phi, cop, prim, doi, cop2, x, cn;
    long long int a, n;
    vector <pair<int,int>> div;

fin = fopen("inversmodular.in", "r");
fout = fopen("inversmodular.out", "w");


    fscanf(fin,"%lld%lld", &a, &n);
    cn=n;
    lim=sqrt(n);
    for(i=2;i<=lim;i++){
        if(n%i==0){
        expo=0;
        cop2=cn;
        do{
        expo++;
        if(n%i==0)
            n/=i;
        }while(n%i==0);
        div.push_back({i, expo});
        div.push_back({cop2/i, expo});

        }
    }

    if(div.size()==0)
    phi=n-1;
    else{
    phi=1;
    for(i=0;i<div.size();i++){
        phi*=(div[i].first-1)*pow(div[i].first, div[i].second-1);
    }
    }
    x=powmod(a, phi-1, cn);
    fprintf(fout,"%d", x);


fclose(fin);
fclose(fout);

    return 0;
}