← 返回题目列表

Codeforces · 140/E

E. 新年花环

中文机器翻译题面 查看原题

由于杰拉尔德、亚历山大、谢尔盖和根纳迪已经忙于通常的新年杂务,爱德华匆忙装饰新年树。任何像样的新年树都必须装饰有好的花环。爱德华有 m 种颜色的灯,他想用它们制作一个花环。该花环应代表一个长度等于 L 的序列。爱德华的树有 n 层高,爱德华计划悬挂该花环,以便用前 l1 盏灯装饰第一层,用接下来的 l2 盏灯装饰第二层,依此类推。最后第 n 层应该用最后 ln 灯装饰,$$\sum_{i=1}^{n} l_i = L.$$

爱德华喜欢各种数学难题,所以他突然想知道:在满足以下两个条件的情况下,花环的组装方式有多少种:

1. 同一层中连续的任意两个灯应具有不同的颜色。
2. 每两个相邻层使用的颜色组必须不同。我们考虑无序集(不是多重集),其中每种颜色出现不超过一次。因此,特定颜色的灯的数量并不重要。

帮助爱德华找到这个棘手问题的答案,否则他将无法在新年之前装饰这棵树。您可能会认为,Edward 拥有无限数量的 m 种颜色的灯,并且不必使用所有 m 种颜色。当表示为序列时,如果花环至少有一个位置不同,则它们被认为是不同的。以 p 为模计算答案。

输入

第一行包含三个整数n、m、p(1≤n,m≤106,2≤p≤109),分别是树的层数,对应的灯的颜色数和模块数。下一行包含 n 个整数 li (1 ≤ li ≤ 5000, $$L = \sum_{i=1}^{n} l_i \leq 10^7$$)。

输出

打印唯一的整数 — 花环的数量以 p 为模。

示例

输入 #1

3 2 1000
3 1 2

输出 #1

8

输入 #2

2 3 1000
2 2

输出 #2

24

输入 #3

1 1 1000
5

输出 #3

0

注意

在第一个示例中,可能有以下变体:121|1|12、121|1|21、121|2|12、121|2|21、212|1|12、212|1|21、212|2|12、212|2|21。在第二个示例中,可能有以下变体:12|13、12|23、12|31、12|32 等。

第一个示例图: