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.

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

Note

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

Abnormal Permutation Pairs (hard version)

Examples