p, n = map(int, input().split())
def pown(i): return pown(i//2)**2*(1, n)[i%2]%p if i else 1
print((pown((p-1)//2)-1)%2)