#include<bits/stdc++.h>
#define LL long long

using namespace std;

ifstream F("inversmodular.in");
ofstream G("inversmodular.out");

LL n,m, ans, MOD, put;

LL po(int x, int p){
    if(p==0)return 1;
    if(p==1)return x;
    LL aux=po(x, p/2);
    LL sol=(1LL*(aux%MOD)*(aux%MOD))%MOD;
    if(p%2) sol = (sol*x)%MOD;
    return sol;
}

LL phi(LL nr)
{
    LL cur = nr;
    for(LL i = 2;i * i <= nr; ++i)
    {
        if (nr % i == 0)
        {
            while(nr % i == 0)nr /= i;
            cur = (cur / i) * (i - 1);
        }
    }
        if (nr != 1) cur = cur / nr * (nr - 1);
    return cur;
}

int main()
{
    F >> n >> m;
    MOD=m;
    put=phi(m)-1;
    ans=po(n, put);
    G << ans;
    return 0;
}