题意

有个圣诞树有层，每一层有个彩灯， 让你用种颜色给彩灯上色，要求圣诞树需要满足下列条件

• 每一层相邻两个彩灯的颜色不一样
• 相邻两层使用的颜色集合不一样

思路

假设我们就一层的话，我们可以用动态规划计算方案数

我们假设表示前个彩灯按顺序用了第种到第种颜色的方案数，转移方程如下

接着我们设表示前层，且第层按顺序用了第种到第种颜色的方案数，同时设表示前层的合法方案数

我们考虑(第一层比较简单), 假设没有第二个约束的话，

但是因为有了第二个约束，就变成了

那么我们就可以计算

代码

/**
 *    author: andif
 *    created: 31.08.2023 23:15:23
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;
const int N = 5006;
// int f[2][N][N], g[2][N];

int main() {
    qc;
    int n, m, p;
    cin >> n >> m >> p;
    vi l(n);
    rep(i, 0, n) cin >> l[i];
    vector<vi> f(N, vi(N, 0));
    vector<vi> g(2, vi(N, 0));
    f[0][0] = 1;
    rep(i, 1, N) {
        rep(j, 1, i + 1) {
            f[i][j] = (1ll * f[i - 1][j] * (j - 1) % p + f[i - 1][j - 1]) % p;
            // dd(i), dd(j), de(f[0][i][j]);
        }
    }
    rep(j, 1, min(l[0], m) + 1) g[0][j] = f[l[0]][j];
    vi F(N);
    F[0] = 1;
    rep(i, 1, N) {
        F[i] = 1ll * F[i - 1] * i % p;
        // dd(i), de(F[i]);
    }
    vi t(m + 1);
    t[0] = 1;
    rep(i, 1, m + 1) {
        t[i] = (1ll * t[i - 1] * (m - i + 1)) % p;
        // dd(i), de(t[i]);
    }
    vi s(n);
    rep(j, 1, min(l[0], m) + 1) {
        s[0] = (s[0] + 1ll * g[0][j] * t[j] % p) % p;
    }
    // de(s[0]);
    rep(k, 1, n) {
        int c = k & 1;
        rep(j, 1, min(l[k], m) + 1) {
            int cur = g[!c][j];
            if (j > l[k - 1]) cur = 0;
            g[c][j] = 1ll * f[l[k]][j] * (s[k - 1] - 1ll * cur * F[j] % p) % p;
            if (g[c][j] < 0) g[c][j] += p;
            // dd(k), dd(j), de(g[c][j]);
        }
        rep(j, 1, min(l[k], m) + 1) {
            s[k] = (s[k] + 1ll * g[c][j] * t[j] % p) % p;
        }
        if (s[k] < 0) s[k] += p;
        // g[!c] = g[c];
    }
    cout << s[n - 1] << '\n';

    return 0;
}