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.

Input

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

Output

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

见题面 Input 部分

见题面 Output 部分

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]$.