#include <iostream>
#include <fstream>
using namespace std;

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

unsigned long long a,n;
unsigned long long phi;

void citire()
{
    in>>a>>n;
}

unsigned long long logPow(unsigned long long b, unsigned long long p)
{
    unsigned long long ans=1;
    while(p)
    {
        if(p%2==1)
            ans*=b;
        b=b*b;
        p=p/2;
    }
    return ans;
}

void rezolvare()
{
    phi=1;
    out<<logPow(a,n-1-phi)%n;
}

int main()
{
    citire();
    rezolvare();
    return 0;
}