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

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