CF140E New Year Garland
题目描述
由于 Gerald、Alexander、Sergey 和 Gennady 已经忙于常规的新年事务，Edward 只好匆忙地装饰新年树。任何像样的新年树都必须用漂亮的彩灯装饰。Edward 有 $m$ 种颜色的灯泡，他想用这些灯泡制作一串彩灯。这串彩灯应当是一个长度为 $L$ 的序列。
Edward 的树有 $n$ 层，他计划将彩灯这样悬挂：用前 $l_1$ 个灯泡装饰第一层，用接下来的 $l_2$ 个灯泡装饰第二层，依此类推。最后第 $n$ 层用最后 $l_n$ 个灯泡装饰。
Edward 热爱各种数学谜题，于是他突然想知道：有多少种不同的方法可以组装这串彩灯，使得同时满足以下两个条件：
1. 同一层中，任意相邻的两个灯泡颜色必须不同。
2. 相邻两层所用颜色的集合必须不同。这里的集合是无序集合（不是多重集），每种颜色最多只出现一次。因此，某种颜色出现多少次并不重要。
请你帮助 Edward 解决这个难题，否则他将无法在新年之前装饰好圣诞树。你可以认为 Edward 拥有每种颜色的灯泡数量无限，也不要求必须用到所有 $m$ 种颜色。如果两个彩灯序列在任意一个位置上不同，则认为它们是不同的。请计算方案数对 $p$ 取模后的结果。
输入格式
第一行包含三个整数 $n$、$m$ 和 $p$（$1 \leq n, m \leq 10^{6}$，$2 \leq p \leq 10^{9}$），分别表示树的层数、灯泡颜色数和取模数。
第二行包含 $n$ 个整数 $l_i$（$1 \leq l_i \leq 5000$，$\sum l_i = L\leq10^7$），表示每层需要的灯泡数量。
输出格式
输出一个整数，表示满足条件的彩灯方案数对 $p$ 取模的结果。
说明/提示
在第一个样例中，可能的方案有：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 等等。
第一个样例的示意图如下：
由 ChatGPT 4.1 翻译