#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;
    b=b%n;
    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 n)
{
    unsigned long long ans=n,i;
    i=2;
    if(n%2==0)
    {
        ans=ans-ans/2;
        while(n%2==0)
            n=n/2;
    }
    for(i=3;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans-ans/i;
            while(n%i==0)
                n=n/i;
        }
    }
    if(n!=1)
        ans=ans-ans/n;
    return ans;
}

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


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