Đêm hôm nay đã là Halloween. Trong khi các bạn của Tỏi đang háo hức khoác lên những bộ hóa trang vô cùng hoành tráng để chơi trò Cho kẹo hay bị ghẹo (Trick or Treat) thì Tỏi đang phải rơi nước mắt với những bài tập toán vô cùng căng thẳng của thầy T giấu tên. Với slogan "Halloween không đáng sợ, TT (tạch toán) mới đáng sợ", Tỏi không thể nào đi chơi cùng các bạn khi chưa hoàn thành xong bài tập của thầy T. Vì thế nên Tỏi đã phải vắng mặt khỏi cuộc vui Halloween năm nay.

Biết người bạn Tỏi của mình đã không thể tham gia buổi săn kẹo hôm nay, hai bạn Tí và Tèo đã "nhận hộ" luôn phần kẹo của Tỏi. Khi cuộc vui đã tàn, tổng kết lại bạn Tí có ~A~ viên kẹo, còn bạn Tỏi có ~B~ viên kẹo. Vì cảm thấy số kẹo đó quá ít ỏi để chia cho cả ba nên hai bạn đã rủ nhau đến gặp phù thủy để bà ta làm phép tăng số lượng viên kẹo này lên. Sau khi phù phép, phù thủy đã hô biến số kẹo tăng lên thành một số là giai thừa của số kẹo ban đầu của mỗi bạn.

Tí và Tèo đã thống nhất rằng số kẹo để chia cho Tỏi sẽ là ước chung lớn nhất của số kẹo hiện tại của hai bạn. Bạn hãy giúp Tí và Tèo tính số kẹo được chia cho Tỏi nhé! Vì kết quả có thể rất lớn nên hãy tính phần dư của số kẹo khi chia cho ~P~.

Dữ liệu

• Gồm một dòng duy nhất chứa ~3~ số nguyên ~A~, ~B~ và ~P~ ~(1 \le A, B \le 10^{12}; 1 \le P \le 10^6)~.

Kết quả

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

• Subtask ~1~ ~(30\%)~: ~1 \le A, B \le 10~.
• Subtask ~2~ ~(40\%)~: ~1 \leq A, B \leq 10^6~.
• Subtask ~3~ ~(30\%)~: ~1 \le A, B \le 10^{12}~.

Ví dụ

Dữ liệu

4 3 127

Kết quả

6

Giải thích

Ta có : ~4! = 24~; ~3! = 6~; ~\gcd(24, 6) \bmod 127 = 6~.