#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

long long a,n,x,nr,lim,sol,i;

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%lld%lld",&a,&n);
    x=nr=n;
    lim=sqrt(n);
    for(i=2;i<=lim;i++)
        if(x%i==0)
        {
            nr=nr*(i-1)/i;
            while(x%i==0) x/=i;
        }
    if(x>1) nr=nr*(x-1)/x;
    nr--;
    sol=1;
    for(i=1;i<=nr;i<<=1)
    {
        if(nr&i) sol=(sol*a)%n;
        a=(a*a)%n;
    }
    printf("%lld",sol);
    return 0;
}