由于杰拉尔德、亚历山大、谢尔盖和根纳迪已经忙于通常的新年杂务,爱德华匆忙装饰新年树。任何像样的新年树都必须装饰有好的花环。爱德华有 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 等。
第一个示例图: