CF1542E2.Abnormal Permutation Pairs (hard version)

This is the hard version of the problem. The only difference between the easy version and the hard version is the constraints on $n$. You can only make hacks if both versions are solved.

A permutation of $1, 2, \ldots, n$ is a sequence of $n$ integers, where each integer from $1$ to $n$ appears exactly once. For example, $[2,3,1,4]$ is a permutation of $1, 2, 3, 4$, but $[1,4,2,2]$ isn't because $2$ appears twice in it.

Recall that the number of inversions in a permutation $a_1, a_2, \ldots, a_n$ is the number of pairs of indices $(i, j)$ such that $i \lt j$ and $a_i \gt a_j$.

Let $p$ and $q$ be two permutations of $1, 2, \ldots, n$. Find the number of permutation pairs $(p,q)$ that satisfy the following conditions:

• $p$ is lexicographically smaller than $q$.
• the number of inversions in $p$ is greater than the number of inversions in $q$.

Print the number of such pairs modulo $mod$. Note that $mod$ may not be a prime.

这是该问题的困难版本。简单版本与困难版本的唯一区别在于对 $n$ 的约束条件。仅当两个版本均被解决时，才允许进行 hack。

$1, 2, \ldots, n$ 的一个排列是指由 $n$ 个整数组成的序列，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。例如，$[2,3,1,4]$ 是 $1, 2, 3, 4$ 的一个排列，但 $[1,4,2,2]$ 不是，因为其中 $2$ 出现了两次。

回顾：排列 $a_1, a_2, \ldots, a_n$ 中的逆序对数量，是指满足 $i \lt j$ 且 $a_i \gt a_j$ 的下标对 $(i, j)$ 的个数。

设 $p$ 和 $q$ 是 $1, 2, \ldots, n$ 的两个排列。求满足以下条件的排列对 $(p,q)$ 的数量：

• $p$ 的字典序小于 $q$；
• $p$ 中的逆序对数量大于 $q$ 中的逆序对数量。

输出该数量对 $mod$ 取模的结果。注意：$mod$ 不一定是质数。

The only line contains two integers $n$ and $mod$ ($1\le n\le 500$, $1\le mod\le 10^9$).

唯一一行包含两个整数 $n$ 和 $mod$（$1\le n\le 500$，$1\le mod\le 10^9$）。

Print one integer, which is the answer modulo $mod$.

输出一个整数，即答案对 $mod$ 取模的结果。

The following are all valid pairs $(p,q)$ when $n=4$.

• $p=[1,3,4,2]$, $q=[2,1,3,4]$,
• $p=[1,4,2,3]$, $q=[2,1,3,4]$,
• $p=[1,4,3,2]$, $q=[2,1,3,4]$,
• $p=[1,4,3,2]$, $q=[2,1,4,3]$,
• $p=[1,4,3,2]$, $q=[2,3,1,4]$,
• $p=[1,4,3,2]$, $q=[3,1,2,4]$,
• $p=[2,3,4,1]$, $q=[3,1,2,4]$,
• $p=[2,4,1,3]$, $q=[3,1,2,4]$,
• $p=[2,4,3,1]$, $q=[3,1,2,4]$,
• $p=[2,4,3,1]$, $q=[3,1,4,2]$,
• $p=[2,4,3,1]$, $q=[3,2,1,4]$,
• $p=[2,4,3,1]$, $q=[4,1,2,3]$,
• $p=[3,2,4,1]$, $q=[4,1,2,3]$,
• $p=[3,4,1,2]$, $q=[4,1,2,3]$,
• $p=[3,4,2,1]$, $q=[4,1,2,3]$,
• $p=[3,4,2,1]$, $q=[4,1,3,2]$,
• $p=[3,4,2,1]$, $q=[4,2,1,3]$.

当 $n=4$ 时，以下均为合法的 $(p,q)$ 对：

• $p=[1,3,4,2]$，$q=[2,1,3,4]$，
• $p=[1,4,2,3]$，$q=[2,1,3,4]$，
• $p=[1,4,3,2]$，$q=[2,1,3,4]$，
• $p=[1,4,3,2]$，$q=[2,1,4,3]$，
• $p=[1,4,3,2]$，$q=[2,3,1,4]$，
• $p=[1,4,3,2]$，$q=[3,1,2,4]$，
• $p=[2,3,4,1]$，$q=[3,1,2,4]$，
• $p=[2,4,1,3]$，$q=[3,1,2,4]$，
• $p=[2,4,3,1]$，$q=[3,1,2,4]$，
• $p=[2,4,3,1]$，$q=[3,1,4,2]$，
• $p=[2,4,3,1]$，$q=[3,2,1,4]$，
• $p=[2,4,3,1]$，$q=[4,1,2,3]$，
• $p=[3,2,4,1]$，$q=[4,1,2,3]$，
• $p=[3,4,1,2]$，$q=[4,1,2,3]$，
• $p=[3,4,2,1]$，$q=[4,1,2,3]$，
• $p=[3,4,2,1]$，$q=[4,1,3,2]$，
• $p=[3,4,2,1]$，$q=[4,2,1,3]$。