Đếm bi

View as PDF

Submit solution

Points: 1.01 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Nguyễn Khánh Việt
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ngoà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)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.