#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

ll A, N;

ll phi(ll n){
    ll rez = n, d = 2;
    while(n > 1){
        if(n % d == 0){
            rez = rez * (d - 1) / d;
            while(n % d == 0){
                n /= d;
            }
        }
        d++;
        if(d * d > n){
            d = n;
        }
    }
    return rez;
}

ll lgput(ll x, ll n){
    if(n == 0){
        return 1;
    }
    else if(n % 2 == 0){
        return lgput(x *x % N, n / 2) % N;
    }
    else{
        return (x * lgput(x *x % N, n / 2) % N) % N;
    }
}

int main(){
    fin>>A>>N;
    fout<<lgput(A % N, phi(N) - 1) % N<<"\n";
    return 0;
}