def Tonelli_Shanks(N,p):
    if (N,p)==(1,2):
        retu=1
    elif pow(N,p>>1,p)==p-1:
        retu=None
    elif p%4==3:
        retu=pow(N,(p+1)//4,p)
    else:
        for nonresidue in range(1,p):
            if pow(nonresidue,p>>1,p)==p-1:
                break
        pp=p-1
        cnt=0
        while pp%2==0:
            pp//=2
            cnt+=1
        s=pow(N,pp,p)
        retu=pow(N,(pp+1)//2,p)
        for i in range(cnt-2,-1,-1):
            if pow(s,1<<i,p)==p-1:
                s*=pow(nonresidue,p>>1+i,p)
                s%=p
                retu*=pow(nonresidue,p>>2+i,p)
                retu%=p
    return retu

P,N=map(int,input().split())
if Tonelli_Shanks(N,P)==None:
    ans=1
else:
    ans=0
print(ans)