Giải bài trực tuyến

Vốn là con nhà có điều kiện nên việc Hoàng fa có hẳn một khu vườn từ khi a mới.......3 tuổi là một việc rất bình thường. Là con người có tâm hồn bay bổng (và thường bay lên cây trong giờ học ), Hoàng fa trồng rất nhiều hoa trong khu vườn của mình. Một ngày nọ, Hoàng cùng các thành viên trong đội tuyển tin đi thăm khu vườn của mình. Vốn rất thích toán, Hoàng fa liền đố Khánh 3508 một bài toán hóc búa như sau: "Giả sử khu vườn này có M loài hoa khác nhau, mỗi loài có vô số bông hoa. E muốn ngắt đủ N bông hoa để tặng cho gấu. A hãy xác định số cách ngắt N bông từ M màu trên, nếu như hoán vị màu sắc các bông hoa trong một cách ngắt chỉ được tính một lần. Do kết quả rất lớn nên chỉ cần in ra phần dư cho một số K cho trước". Vốn có ác cảm với những bông hoa (do trong quá khứ từng phải đếm số cánh hoa để xác định xem có nên tắm hay không) và trong tay Khánh 3508 chỉ có một chiếc iPad Air cùi bắp khiến cho việc tính toán trở nên vô cùng khó khăn. Bởi vậy, Khánh 3508 rất cần tới sự giúp đỡ của bạn, để trả lời chính xác câu hỏi của Hoàng fa.

Input

Gồm ba số nguyên N, M và K

Output

Số cách ngắt đủ N bông hoa, giả sử N bông hoa có thể không đủ M màu hoa.

Example

Input:
3 3 1000
Output:
10
 
Giải thích test 1:
Đánh số các màu hoa từ 1..3
->các cách ngắt sẽ là:
(1;1;1) (1;1;2) (1;1;3) (1;2;2) (1;2;3)
(1;3;3) (2;2;2) (2;2;3) (2;3;3) (3;3;3)

Giới hạn :
Task 1: N,M<=104, K<=1018 (15 test)
Task 2: N,M<=106, K<=109 (15 test)
Task 3: N,M<=109, K<=108 (K là một số nguyên tố)  (20 test)