#pragma GCC optimize ("03", "Ofast", "unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define INFILE "inversmodular.in"
#define OUTFILE "inversmodular.out"

typedef long long ll;

ll getPhi(int number){
    int ans = number;
    for(int d = 2; d * d <= number; ++d){
        if(number % d == 0){
            ans = ans / d * (d - 1);
            while(number % d == 0) number /= d;
        }
    }
    if(number != 1) ans = ans / number * (number - 1);
    return ans;
}

ll lgput(ll number, ll exponent, ll MOD){
    ll ans = 1;
    while(exponent){
        if(exponent & 1) ans = (ans * number) % MOD;
        number = (number * number) % MOD;
        exponent >>= 1;
    }
    return ans;
}

void solve(){

    int n, MOD; cin >> n >> MOD;
    cout << lgput(n, getPhi(MOD) - 1, MOD);

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}