#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 read()
{
    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=(ans*b)%n;
        b=(b*b)%n;
        p=p/2;
    }
    return ans;
}

unsigned long long getPhi(unsigned long long x)
{
    unsigned long long ans=1;
    unsigned long long i,nr;
    unsigned long long xCopy=x;
    i=2;
    nr=0;
    while(xCopy%i==0)
    {
        xCopy=xCopy/i;
        nr++;
    }
    ans=ans*(nr+1);
    for(i=3;(i-1)*(i-1)<=x;i+=2)
    {
        nr=0;
        while(xCopy%i==0)
        {
            xCopy=xCopy/i;
            nr++;
        }
        ans*=(nr+1);
    }
    return x-ans;
}

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

int main()
{
    read();
    solve();
    return 0;
}