#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long A,n;

long long getphi(long long nr){
    long long sol = nr,i;
    for(i = 2; i*i <= n; i++){
        if(nr%i == 0){
            while(nr%i == 0){
                nr/=i;
            }
            sol -= sol/i;
        }
    }
    if(nr != 1){
        sol -= sol/nr;
    }
    return sol;
}

int main()
{
    long long i,phi,sol,put;
    fin>>A>>n;
    phi = getphi(n);
    phi--;
    sol = 1;
    put = A;
    while(phi!=0){
        if(phi%2==1){
            sol = (sol*put)%n;
        }
        put = (put*put)%n;
        phi /= 2;
    }
    fout<<sol<<'\n';
    return 0;
}