#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int n,a;
int phi(int n){
    return n-1;
}
ll pwr(ll nr,ll p){
    ll rez=1;
    while(p){
        if(p&1)rez*=nr;
        p=p>>1;
        nr*=nr;
        rez=rez%n;
        nr=nr%n;
    }
    return rez;
}

int main(){
    in>>a>>n;
    out<<pwr(a,phi(n)-1);
}