E2. 异常排列对（困难版）
时间限制：4 秒
内存限制：512 MB

本题是困难版。简单版与困难版的唯一区别在于对 $n$ 的限制不同。只有两个版本均通过，才能进行 hack。

一个 $1,2,\dots,n$ 的排列是一个由 $n$ 个整数组成的序列，其中 $1$ 到 $n$ 的每个整数恰好出现一次。例如，$[2,3,1,4]$ 是 $1,2,3,4$ 的一个排列，但 $[1,4,2,2]$ 不是，因为 $2$ 出现了两次。

回顾一下，排列 $a_1,a_2,\dots,a_n$ 中的逆序数是满足 $i<j$ 且 $a_i > a_j$ 的索引对 $(i,j)$ 的数量。

设 $p$ 和 $q$ 是 $1,2,\dots,n$ 的两个排列。求满足以下条件的排列对 $(p,q)$ 的数量：

• $p$ 的字典序小于 $q$；
• $p$ 的逆序数大于 $q$ 的逆序数。

输出答案对 $\textit{mod}$ 取模的结果。注意 $\textit{mod}$ 不一定为素数。

输入
仅一行，包含两个整数 $n$ 和 $\textit{mod}$（$1 \le n \le 500$，$1 \le \textit{mod} \le 10^9$）。

输出
一个整数，表示答案对 $\textit{mod}$ 取模的结果。

示例
输入

4 403458273

输出

17

注释
当 $n=4$ 时，所有有效的排列对 $(p,q)$ 如下：

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