Abnormal Permutation Pairs (hard version)
Contest: Codeforces Round 729 (Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dp, fft, math

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 format:
The only line contains two integers $$$n$$$ and $$$mod$$$ ($$$1\le n\le 500$$$, $$$1\le mod\le 10^9$$$).

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

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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

Example input:
4 403458273

Example output:
17

Editorial:
We recommend you to read E1's editorial first.
Let's directly count the number of permutation pairs $$$(p,q)$$$ of length $$$n$$$ with $$$inv(p)-inv(q)=k$$$, instead of counting it indirectly from "the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$.". Call this number $$$f(n,k)$$$.
We have an $$$n^4$$$ transition: $$$f(n,k)=\sum_{i<n} f(n-1,k-i)\times |n-i|$$$ (Consider where to insert $$$n$$$ in the first and second permutation. If the two places are indices $$$(I,J)$$$, then the delta of $$$inv(p)$$$ is $$$n-I$$$, the other is $$$n-J$$$, so the delta of difference is $$$J-I$$$. In $$$[1,n]$$$ there are $$$n-|J-I|$$$ pairs of integers with difference $$$J-I$$$.)
Let's speed it up. When $$$f(n,k)$$$ moves to $$$f(n,k+1)$$$, it looks like this: ($$$n=4$$$, as an example)
- $$$f(n-1,k-3)\times 1+f(n-1,k-2)\times 2+f(n-1,k-1)\times 3+f(n-1,k)\times 4+f(n-1,k+1)\times 3+f(n-1,k+2)\times 2+f(n-1,k+3)\times 1$$$ - $$$f(n-1,k-2)\times 1+f(n-1,k-1)\times 2+f(n-1,k)\times 3+f(n-1,k+1)\times 4+f(n-1,k+2)\times 3+f(n-1,k+3)\times 2+f(n-1,k+4)\times 1$$$
So with prefix sums $$$s$$$ ($$$s(i,j)=\sum_{k\le j} f(i,k)$$$) we can write $$$f(n,k+1)=f(n,k)-(s(n-1,k)-s(n-1,k-n))+(s(n-1,k+n)-s(n-1,k))$$$.
Note that the second indice of the array might be negative, so we should shift it by $$$130000$$$.