#include <fstream>

using namespace std;

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

int main()
{
    int n,a,nc,v[10],k=0,i,j;
    f>>a>>n;
    nc=n;
    if(!(nc%2))
    {
        k++;
        v[k]=2;
        while(!nc%2)
            nc/=2;
    }
    i=3;
    for(i=3;i*i<=n;i+=2)
    {
        if(!(nc%i))
        {
            k++;
            v[k]=i;
            while(!(nc%i))
                nc/=i;
        }
    }
    if(!k)
    {
        k++;
        v[k]=n;
    }
    if(k==1)
        j=n-1;
    else
    {
        j=n;
        for(i=1;i<=k;i++)
            {
                j/=v[i];
                j*=v[i]-1;
            }
    }
    j--;
    long long x=a,x1=1;
    while(j)
    {
        if(j%2)
        {
            x1*=x;
            x1%=n;
            x*=x;
            x%=n;
            j/=2;
        }
        else
        {
            j/=2;
            x*=x;
            x%=n;
        }
    }
    g<<x1;
    return 0;
}