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

return rasp;
}

int powmod(int baza, 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 a, n, i, lim, expo, phi, cop, prim, doi, cop2, x, cn;

    vector <pair<int,int>> div;

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


    fscanf(fin,"%d%d", &a, &n);
    lim=sqrt(a);
    cn=n;
    for(i=2;i<=n;i++){
        if(n%i==0){

        expo=0;
        cop=n;
        cop2=1;
        do{
        expo++;
        cop/=i;
        cop2*=i;
        }while(cop%i==0);
        n/=cop2;
        div.push_back({i, expo});
        }
    }

    phi=1;
    for(i=0;i<div.size();i++){
        prim=div[i].first;
        doi=div[i].second;
        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;
}