#include <fstream>

using namespace std;

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

int a,n;

int phii(long long x)
{
    int phi=x;
    int copx=x;
    for(int i=2;1LL * i*i<=copx;i++)
    {
        if(x%i==0)
        {
            while(x%i==0)
            {
                x/=i;
            }
            phi=phi/i*(i-1);
        }
    }
    if(x>1)
    {
        phi=phi/x*(x-1);
        ///putem avea un singur numar mai mare decat radical din x
    }
    return phi;
}

long long lgput(long long a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
    {
        long long jumatate=lgput(a,exp/2);
        return jumatate*jumatate%n;
    }
    else
    {
        long long putere=lgput(a,exp-1);
        return putere*a%n;
    }
}

int main()
{
    in>>a>>n;
    int phiii=phii(n);
    out<<lgput(a,phiii-1);
    return 0;
}