E2. Аномальные пары перестановок (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между простой и сложной версиями заключается в ограничениях на $$$n$$$. Вы можете делать взломы, только если решили обе версии этой задачи.

Перестановка чисел $$$1, 2, \ldots, n$$$ – это последовательность из $$$n$$$ целых чисел, в которой каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз. Например, $$$[2,3,1,4]$$$ является перестановкой $$$1, 2, 3, 4$$$, но $$$[1,4,2,2]$$$ – не перестановка, поскольку $$$2$$$ встречается здесь дважды.

Напомним, что количеством инверсий в перестановке $$$a_1, a_2, \ldots, a_n$$$ называется число пар индексов $$$(i, j)$$$ таких, что $$$i < j$$$ и $$$a_i > a_j$$$.

Пусть $$$p$$$ и $$$q$$$ – две перестановки чисел $$$1, 2, \ldots, n$$$. Найдите количество пар перестановок $$$(p,q)$$$, удовлетворяющих следующим условиям:

  • $$$p$$$ лексикографически меньше $$$q$$$.
  • Количество инверсий в $$$p$$$ больше, чем в $$$q$$$.

Выведите это количество пар по модулю $$$mod$$$. Обратите внимание, что $$$mod$$$ – не обязательно простое число.

Входные данные

В единственной строке содержатся два целых числа $$$n$$$ и $$$mod$$$ ($$$1\le n\le 500$$$, $$$1\le mod\le 10^9$$$).

Выходные данные

Выведите одно целое число — ответ на задачу по модулю $$$mod$$$.

Пример
Входные данные
4 403458273
Выходные данные
17
Примечание

Все возможные пары перестановок $$$(p,q)$$$ при $$$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]$$$.