Abnormal Permutation Pairs (hard version)

给定 $n,m$,求有多少对长度为 $n$ 的排列 $p,q$，满足以下条件。 - $p$ 的字典序小于 $q$ - $p$ 的逆序对个数 **严格大于** $q$. 答案对 $m$ 取模。 $1\le n\le 500,1\le m\leq 10^9$，**不保证** $m$ 为素数。

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

4 403458273

17

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