Trong lý thuyết số, ký hiệu Legendre \left(?rac{a}{p} ight)\(cho biếtacó là thặng dư bình phương modulo\)p hay không. Hãy tính ký hiệu Legendre.

Định dạng đầu vào

• Một dòng: \(a, p\) (\(p\) nguyên tố lẻ).

Định dạng đầu ra

• 1 nếu QR, \(-1\) nếu không, 0 nếu \(a \equiv 0\).

Ví dụ

Input:

2 7

Output:

1

Ràng buộc

• 100% số điểm: \(p \le 10^{9}\).