#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
 
int a, n, idk = 1, d = 2, p, mod;
 
void euler(int n){
 
    while(n > 1){
        p = 0;
        while(n % d == 0)
            n /= d, p++;
        
        if(p)
            idk = idk * pow(d, p - 1) * (d - 1);
        d++;
        if(d * d > n)
            d = n;
    }
}
 
int exp_rap(int a, int n){
 
    int p = 1;
    while(n){
        if(n % 2 == 1)
            p = (long long) p * a % mod;
        a = (long long) a * a % mod;
        n /= 2;
    }
 
    return p;
}
 
int main(){
 
    fin >> a >> n;
    mod = n;
    euler(n);
    fout << exp_rap(a, idk - 1);
}