#include<cstdio>

using namespace std;

typedef long long int lld;

void Read(),Print();

int A,N;

int ExpLog(int B,int E)
{
    if(E == 0) return 1;
    if(E == 1) return B;
    int t = ExpLog(B,E/2);
    return (1LL * t * t * ExpLog(B,E%2))%N;
}

lld Phi(int X)
{
    int p;
    lld ans = X;
    for(p = 2; p * p <= X; p++)
        if(X%p == 0) ans = ans / p * (p - 1), X /= p;
    if(X > 1) ans = ans / X * (X - 1);
    return ans;
}

int main()
{
    Read();
    Print();

    return 0;
}

void Read()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%d%d",&A,&N);
}

void Print()
{
    printf("%d\n",ExpLog(A,Phi(N) - 1));
}