#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct pp{
    int n, p;
    int np = 1;
    pp(){}
    pp(int n, int p) : n(n), p(p){}
};

int n;
vector<pp> pps;
void spliterup(int a){
    for(int i = 2; i*i <= a; i++){
        pp x(i, 0);
        while(a % i == 0){
            x.p++;
            x.np *= i;
            a /= i;
        }
        
        if(x.p != 0){
            pps.push_back(x);
        }
    }
    
    if(a != 1){
        pp x(a, 1);
        x.np *= a;
        pps.push_back(x);
    }
}

int yesnt(long long a){
    for(auto b : pps){
        a *= (b.np - b.np/b.n);
    }
    for(auto b : pps){
        a /= b.np;
    }
    return a;
}

int kapow(int a, int p){
    int r = 1;
    int cc = a;
    while(a > 0){
        if(a & 1){
            r *= cc;
            r %= n;
        }
        cc *= cc;
        cc %= n;
        a >>= 1;
    }
    return r;
}

int main()
{
    int a;
    fin >> a >> n;
    
    spliterup(n);
    
    fout << kapow(a, yesnt(n)-1);
    return 0;
}