#include <bits/stdc++.h>

using namespace std;

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

int a,b,mod;

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

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

    if(x%2==0)
    {
        p=p/2;
        while(x%2==0)
            x/=2;
    }

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

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

    return p;
}

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

    mod=b;
    b=Phi(b);

    fout<<1LL*Lgput(a,b-1)%mod;
    return 0;
}