Tìm số nguyên dương \(x\) nhỏ nhất thỏa mãn đồng thời: \(x \equiv 1 \pmod{a}\), \(x \equiv 2 \pmod{b}\), \(x \equiv 3 \pmod{c}\) với \(a, b, c\) đôi một nguyên tố cùng nhau.

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

• Một dòng chứa ba số nguyên \(a, b, c\) (\(2 \le a, b, c \le 10^{9}, \gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1\)).

Định dạng đầu ra

• Một số nguyên là \(x\) nhỏ nhất (\(x \ge 0\)).

Ví dụ

Input:

3 5 7

Output:

52

Giải thích: \(52 \equiv 1 \pmod{3}, 52 \equiv 2 \pmod{5}, 52 \equiv 3 \pmod{7}\).

Ràng buộc

• 100% số điểm: \(c \le 10^{9}\), tích \(\le 10^{18}\).