#include <bits/stdc++.h>

using namespace std;

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

int phi(int x){
    int answer = x;

    for(int i=2; i<=x/i; i++)
        if(x%i == 0){
            answer -= answer / i;
            while(x%i == 0)
                x /= i;
        }
    if(x > 1)
        answer -= answer / x;

    return answer;
}

int lgput(int a, int b, int mod){
    int answer = 1;
    while(b != 0){
        if(b&1)
            answer = (long long)answer * a % mod;
        a = (long long)a * a % mod;
        b >>= 1;
    }
    return answer;
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    int a, b, mod;
    fin>>a>>mod;
    b = phi(mod) - 1;
    fout<<lgput(a, b, mod);
    return 0;
}