CF140E.New Year Garland

As Gerald, Alexander, Sergey and Gennady are already busy with the usual New Year chores, Edward hastily decorates the New Year Tree. And any decent New Year Tree must be decorated with a good garland. Edward has lamps of m colors and he wants to make a garland from them. That garland should represent a sequence whose length equals L. Edward's tree is n layers high and Edward plans to hang the garland so as to decorate the first layer with the first _l_1 lamps, the second layer — with the next _l_2 lamps and so on. The last n-th layer should be decorated with the last l__n lamps,

Edward adores all sorts of math puzzles, so he suddenly wondered: how many different ways to assemble the garland are there given that the both following two conditions are met:

1. Any two lamps that follow consecutively in the same layer should have different colors.
2. The sets of used colors in every two neighbouring layers must be different. We consider unordered sets (not multisets), where every color occurs no more than once. So the number of lamps of particular color does not matter.

Help Edward find the answer to this nagging problem or else he won't manage to decorate the Tree by New Year. You may consider that Edward has an unlimited number of lamps of each of m colors and it is not obligatory to use all m colors. The garlands are considered different if they differ in at least one position when represented as sequences. Calculate the answer modulo p.

由于杰拉尔德、亚历山大、谢尔盖和根纳季正忙于惯常的新年事务，爱德华急忙装饰新年树。而一棵体面的新年树必须用一条精美的花环来装饰。爱德华拥有 $m$ 种颜色的灯泡，他想用这些灯泡制作一条花环。该花环应表示一个长度为 $L$ 的序列。爱德华的树共有 $n$ 层高，他计划将花环悬挂起来，使得第一层用前 $l_1$ 个灯泡装饰，第二层用接下来的 $l_2$ 个灯泡装饰，依此类推。第 $n$ 层（即最后一层）应用最后的 $l_n$ 个灯泡装饰，

爱德华酷爱各类数学谜题，因此他突然想到：在满足以下两个条件的前提下，有多少种不同的方式来组装这条花环？

1. 同一层中任意两个相邻的灯泡颜色必须不同；
2. 任意两个相邻层所使用的颜色集合必须互不相同。我们考虑的是无序集合（而非多重集），其中每种颜色至多出现一次。因此，某种颜色所用灯泡的具体数量无关紧要。

请帮助爱德华解决这个令人困扰的问题，否则他将无法在新年之前完成树的装饰。你可以认为爱德华拥有每种颜色的灯泡数量均无限，并且不强制要求使用全部 $m$ 种颜色。若两条花环作为序列表示时至少有一个位置上的灯泡颜色不同，则视为不同的花环。请将答案对 $p$ 取模后输出。

The first line contains three integers n, m and p (1 ≤ n, m ≤ 106, 2 ≤ p ≤ 109) which are the number of the tree's layers, the number of the lamps' colors and module correspondingly. The next line contains n integers l__i (1 ≤ l__i ≤ 5000, ).

第一行包含三个整数 $n$、$m$ 和 $p$（$1 ≤ n, m ≤ 10^6$，$2 ≤ p ≤ 10^9$），分别表示树的层数、灯的颜色种类数以及模数。
下一行包含 $n$ 个整数 $l_i$（$1 ≤ l_i ≤ 5000$，）。

Print the only integer — the number of garlands modulo p.

输出唯一的整数——花环数量对 $p$ 取模的结果。

In the first sample the following variants are possible: 121|1|12, 121|1|21, 121|2|12, 121|2|21, 212|1|12, 212|1|21, 212|2|12, 212|2|21. In the second sample the following variants are possible: 12|13, 12|23, 12|31, 12|32 and so on.

Figure for the first sample:

在第一个样例中，可能的划分方式如下：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，等等。

第一个样例的示意图：