#include <bits/stdc++.h>

using namespace std;

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

int a,b;

int Lgput(int x,int n)
{
    int p=1;
    while(n>0)
    {
        if(n%2==1)p=p*x;
        x=x*x;
        n/=2;
    }
    return p;
}

int Phi(int x)
{
    double p;
    int div;
    p=x;

    div=2;
    while(div*div<=x && x>1)
    {
        if(x%div==0)
        {
            p=p*((div-1)/div);
            while(x%div==0)
                x/=div;
        }
        div++;
    }

    if(x>1)p=p*(x-1)/x;
    return p;
}

int main()
{
    fin>>a>>b;

    int modulo=b;
    b=Phi(b);

    fout<<Lgput(a,b-1)%modulo;
    return 0;
}