#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define int long long

using namespace std;

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

int a, b, MOD;

int phi(int n){
    int answer = n;
    for(int i=2; i<=n/i; i++)
        if(n % i == 0){
            answer -= answer / i;
            while(n % i == 0)
                n /= i;
        }
    if(n != 1)
        answer -= answer / n;
    return answer;
}

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

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

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