登录/注册
225. 多重集组合数(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 141 | 通过次数: 79
尝试人数: 38 | 通过人数: 37
标签: 动态规划
难度: 中等
2
3

nn 种物品,第 ii 种物品有 aia_i 个。

不同种类的物品可以互相区分但相同种类的无法区分。从这些物品中取出 mm 个物品的话,有多少种取法?

求出方案数模 MM 的余数。

输入

  • 输入第一行有三个整数nnmmMM, 第二行有nn个整数,表示数组aia_i
  • 1n10001 \leq n \leq 1000
  • 1m10001 \leq m \leq 1000
  • 1ai10001 \leq a_i \leq 1000
  • 2M100002 \leq M \leq 10000

输出

  • 输出一个整数,表示方案数模 MM 的余数
样例 1
输入
3 3 10000
1 2 3
输出
6