Trong lý thuyết số, ký hiệu Legendre \(\left(?rac{a}{p} ight)\) cho biết \(a\) có 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\).