Hide

Problem A
Jacobi Symbol

Languages en is

Compute the Jacobi Symbol $\left(\frac{a}{b}\right)$.

Input

First line consist of an integer $-2^{31} \leq a \leq 2^{31}-1$. The second line consists of an odd integer $3 \leq b \leq 2^{31}-1$.

Output

Write a single line with $\left(\frac{a}{b}\right) \in \{ -1,0,1\} $.

Sample Input 1 Sample Output 1
-15750
37907
1