New Year Garland

题意翻译

现在小 $A$ 手上有 $m$ 种小球，他要用这些小球装饰一棵圣诞树。 这是一棵神奇的圣诞树，一共有 $n$ 层，每层由 $l_i$ 个小球组成。 对于每一层内部，相邻的小球的都不相同。 同时，外部来看，相邻的两层的小球集合不相同。 现在小 $A$ 想要知道一共有多少种合法装饰方案，答案对 $p$ 取模。 数据范围： ($1≤n,m≤10^6,2≤p≤10^9,1≤l_i≤5000,\sum\limits^n_{i=1}l_i≤10^7$)

题目描述

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 $ .

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ p $ ( $ 1<=n,m<=10^{6} $ , $ 2<=p<=10^{9} $ ) 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 $ , ).

输出格式

Print the only integer — the number of garlands modulo $ 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

说明

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: 

题意翻译

现在小 $A$ 手上有 $m$ 种小球，他要用这些小球装饰一棵圣诞树。 这是一棵神奇的圣诞树，一共有 $n$ 层，每层由 $l_i$ 个小球组成。 对于每一层内部，相邻的小球的都不相同。 同时，外部来看，相邻的两层的小球集合不相同。 现在小 $A$ 想要知道一共有多少种合法装饰方案，答案对 $p$ 取模。 数据范围： ($1≤n,m≤10^6,2≤p≤10^9,1≤l_i≤5000,\sum\limits^n_{i=1}l_i≤10^7$)