#include <cstdio>
using namespace std;
int a,n,d,p;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d %d\n",&a,&n);
    p=1;
    for(d=2;d*d<=n;d++)
        if(!(n%d))
        {
            while(n%d==0)
                n/=d;
            p*=(d-1);
            if(n==1)
                break;
        }
    if(n!=1)
        p=n-1;
    p--;
    d=1;
    while(p)
    {
        if(p%2==1)
            d=(d*a)%n;
        a=(a*a)%n;
        p/=2;
    }
    printf("%d\n",d);
    return 0;
}