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 < j$ and $a_i > 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.

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

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