Đếm bi
Xem dạng PDFNgoài sở thích sử dụng dầu ăn để nấu cơm giúp mẹ, Khải còn một sở thích khác mà ít người biết tới, đó là sưu tầm bi. Cũng bởi vậy, sau nhiều năm tìm tòi, nghiên cứu, trấn lột và trao đổi bi với lũ trẻ trong xóm, Khải đã có ~N~ viên bi giống hệt nhau, cả về màu sắc lẫn kích thước. Lo sợ mẹ sẽ quẳng hết bi của mình cho ve chai nên cậu lên kế hoạch để ~N~ viên bi vào ~M~ hộp giống nhau cho mẹ khó tìm, tất nhiên số bi trong các hộp có thể là khác nhau, dẫn tới việc có hộp có đủ ~N~ viên bi, hoặc có hộp không có viên bi nào. Đến khi chia bi vào hộp, cậu bỗng nảy ra một câu hỏi, liệu sẽ có bao nhiêu cách chia ~N~ viên bi giống nhau và ~M~ chiếc hộp. Câu hỏi khó đó khiến cho Khải cả ngày bẩn thẩn bần thần, liên tục giảm cân, học hành sa sút. Khải rất cần tới sự giúp đỡ của bạn, một Vcoder tài năng, để có thể trả lời chính xác số cách chia bi mà cậu ấy đang muốn tính, do kết quả rất lớn mà Khải lại không thể nhớ được những con số lớn nên Khải chỉ cần bạn in ra phần dư của số cách chia bi cho một số nguyên ~K~ cho trước.
Input
Gồm ~3~ số nguyên ~N~, ~M~ và ~K~.
Output
Một dòng duy nhất là số cách chia bi.
Giới hạn
- Sub ~1~: ~(10~ test) ~n~, ~m \le 300~, ~k \le 10^{9}~.
- Sub ~2~: ~(10~ test) ~n~, ~m \le 2000~, ~k \le 10^{9}~.
- Sub ~3~: ~(10~ test) ~n~, ~m \le 10^{5}~, ~k \le 10^{9}~.
- Sub ~4~: ~(10~ test) ~n~, ~m \le 2 \times 10^{7}~, ~k = 10^{9} + 7~
Sample Input
2 2 1000
Sample Output
3
Note
Có 3 cách chia bi là: ~(2-0), (0-2)~ và ~(1-1)~.
Bình luận
Comment này spoil thuật (Mình sẽ không đề cập tới cách làm chi tiết những sẽ có gợi ý hướng làm cho bài)