New Year Garland

题号：NC229278
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

用 $m$ 种颜色的彩球装点 $n$ 层的圣诞树。圣诞树的第 $i$ 层恰由 $l_{i}$ 个彩球串成一行，且同一层内的相邻彩球颜色不同，同时相邻两层所使用彩球的颜色集合不同。求有多少种装点方案，答案对 $p$ 取模。

第一行包含三个整数，分别表示树的层数、灯的颜色数和模数。
第二行包含 个整数。
保证

输出一个整数表示答案

示例1

复制

3 2 1000
3 1 2

复制

在这个示例中，以下方案是可能的：121|1|12、121|1|21、121|2|12、121|2|21、212|1|12、212|1|21、212|2|12、212|2|21

示例2

复制

2 3 1000
2 2

复制

在这个示例中，以下方案是可能的：12|13、12|23、12|31、12|32 等等

示例3

复制

1 1 1000
5

复制

原题链接：https://codeforces.com/problemset/problem/140/E