#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 nn){
    int rez=nn;
    for(int i=2;i*i<=nn;i++){
        if(n%i==0){
            while(n%i==0)nn/=i;
            rez-=rez/i;
        }
    }
    if(nn>1)rez-=rez/nn;
    return rez;
}
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);
}