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

    }
    so<<val;
    si.close();
    so.close();
    return 0;
}