#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");

int mod;

int phi(int a)
{
    int i,nr=a;

    for(i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            nr=nr/i*(i-1);
            while(a%i==0)
                a/=i;
        }
    }
    if(a!=1)
        nr=nr/a*(a-1);

    return nr;
}


int fast_expo(int nr, int exponent)
{
    if(exponent==1)
        return nr;
    else if(exponent%2)
        return (nr*fast_expo(nr,exponent-1))%mod;
    else
    {
        int a=fast_expo(nr,exponent/2);
        return (a*a)%mod;
    }
}


int invers_modular(int a, int m)
{
    mod=m;
    m=phi(m)-1;
    return fast_expo(a,m);
}


int main()
{
    int n,nr;
    fin>>nr>>n;
    fout<<invers_modular(nr,n)<<'\n';

    return 0;
}