运用 Dilworth 定理，转化为求满足最长下降子序列长度不超过 $3$ 的排列数量。

考虑如何刻画排列，是一个非常经典的 trick，维护一个空序列，每次在末尾插入大小不超过序列长度加一的一个数 $x$，并将原来序列中的所有 $\ge x$ 的数加一，最后一定能得到一个排列。其实就是在实时维护相对排名。

这样做的一个好处是，对于长度为 $i$ 的所有最长下降子序列，我们只关注结尾值最大的一个位置，因为我们是从末尾插入，新加入的数可以接在前面任何一个数后面，所以长度相同的下降子序列，最后一个数越大能表示的限制越多。

设 $f_{i,j,k}$ 表示 $1\sim i$ 的排列，长度为 $2$ 的最长下降子序列末尾值最大排名为 $j$，长度为 $3$ 的最长下降子序列末尾值最大排名为 $k$，新加入末尾的数为 $l$，根据 $l\in(k+1,j),(j+1,i],[i+1,i+1]$ 的取值去朴素转移，可以 $O(n^4)$，就是现在提交记录里 TLE 80 的代码。

不难发现转移的三个部分可以看成对下一个阶段的 dp 数组做单点加，一列加，一行加，用二维差分可以优化到 $O(n^3)$，但是可能被卡常了。

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, mod, dp[N][N][N], ans;
long long c[N][N]; 
void add(int x, int y, int X, int Y, int v) {
    c[x][y] += v;
    c[x][Y + 1] -= v;
    c[X + 1][y] -= v;
    c[X + 1][Y + 1] += v;
    return;
}
int main(){
    freopen("great.in", "r", stdin);
    freopen("great.out", "w", stdout);
    cin >> n >> mod;
    dp[0][0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= i; k++) {
                if (!dp[i][j][k]) continue;
                (dp[i + 1][j][k] += dp[i][j][k]) %= mod;
                add(j + 1, k + 1, j + 1, j, dp[i][j][k]);
                add(j + 1, k, i, k, dp[i][j][k]);
            }
        }
        for (int j = 0 ; j <= i + 1; j++) {
            for (int k = 0; k <= i + 1; k++) {
                if (j) c[j][k] += c[j - 1][k];
                if (k) c[j][k] += c[j][k - 1];
                if (j && k) c[j][k] -= c[j - 1][k - 1];
                (dp[i + 1][j][k] += c[j][k] % mod) %= mod;
            }
        }
        for (int j = 0 ; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                c[j][k] = 0; 
            }
        }
    }
    for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
            (ans += dp[n][j][k]) %= mod;
        }
    }
    ans = (ans % mod + mod) % mod;
    cout << ans << '\n';
    return 0;
}