#include<fstream>
#include<iostream>
#define ll long long
using namespace std;
ifstream si("inversmodular.in");
ofstream so("inversmodular.out");
ll phi(ll val)
{
    ll crt=val;
    ll i;
    if(val%2==0)
    {
        while(val%2==0)
        {
            val/=2;
        }
        crt/=2;
    }
    for(i=3;i*i<=val;i+=2)
    {
        if(val%i==0)
        {
            while(val%i==0)
            {
                val/=i;
            }
            crt=(crt/i)*(i-1);
        }
    }
    if(val!=1)
    {
        crt=crt/val*(val-1);
    }
    return crt;
}
int main()
{

    ll n,m;
    si>>n>>m;
    ll put=phi(m)-1;
    ll val=1;
    while(put)
    {
        if(put&1)
        {
            val=(val*n)%m;
        }
        n=(n*n)%m;
        put>>=1;
    }
    so<<val;
    si.close();
    so.close();
    return 0;
}