#include <cstdio>

using namespace std;

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    int i,a,mod,n,div=0;
    scanf("%d %d",&a,&n);
    mod=n;

    int fi=n;

    for(i=2;i*i<=n;++i)
    {
        if(n%i==0){
        while(n%i==0)n/=i;
        fi=(fi/i)*(i-1);
        }
    }
    if(n!=1)
        fi=(fi/n)*(n-1);
    n=fi-1;

    long long ans=1,x=a;
    while(n>0)
   {
        if(n%2==1)
            ans=ans*x%mod;
        n=n/2;
        x=x*x%mod;
    }

    printf("%d",ans);

    return 0;
}