#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long phi(long long n){
    long long res=n;
    for(int i=2;i*i<=n;++i){
        if(n%i==0){
            res*=(i-1);
            res/=i;
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1){
        res*=(n-1);
        res/=n;
    }
    return res;
}

long long put(long long a, long long n){
    long long p=1;
    while(n){
        if(n%2){
            p=p*a;
        }
        a=a*a;
        n/=2;
    }
    return p;
}

int main(){
    long long a, n;
    f >> a >> n;
    g << put(a, phi(n)-1)%n;
    return 0;
}