D. Удаление токенов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
r-906 & Hatsune Miku - All I Can See Is You

Назовём последовательность целых чисел $$$a$$$ валидной, если и только если $$$\forall 1 \le i \le n, 0 \le a_i \le i$$$.

Для валидной последовательности $$$a$$$ длины $$$n$$$ определим вес $$$f(a)$$$:

  • Изначально токен помещается на каждую целочисленную точку отрезка $$$[1, n]$$$ числовой оси.
  • Выполните последовательно $$$n$$$ операций. Во время $$$i$$$-й операции, если $$$a_i \ne 0$$$, удалите на отрезке $$$[a_i, i]$$$ токен, который ещё не был удалён; иначе ничего не делайте.
  • $$$f(a)$$$ — это количество способов удалить токены. Два способа считаются различными, если существует $$$t$$$, такой что позиции токенов, удалённых двумя способами, различны на $$$t$$$-й операции.

Например, $$$f([0, 2, 1]) = 2$$$, потому что мы можем последовательно удалить токены на позициях $$$2, 1$$$ или $$$2, 3$$$.

JT даёт вам два целых числа $$$n, m$$$ и просит вас найти сумму весов всех $$$(n + 1)!$$$ валидных последовательностей длины $$$n$$$. Поскольку ответ может быть очень большим, выведите его по модулю $$$m$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5000, 10^8 \le m \le 1.01 \cdot 10^9$$$) — длина валидных последовательностей и модуль.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$2.5 \cdot 10^7$$$.

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

Для каждого набора входных данных выведите целое число — сумму весов всех $$$(n + 1)!$$$ валидных последовательностей длины $$$n$$$, по модулю $$$m$$$.

Пример
Входные данные
6
1 1000000007
2 1000000007
3 1000000007
4 1000000007
5 1000000007
114 514191981
Выходные данные
2
7
37
273
2672
393775292
Примечание

В первом наборе входных данных валидные последовательности — это $$$[0]$$$ и $$$[1]$$$, и ответ равен $$$f([0]) + f([1]) = 1 + 1 = 2$$$.

Во втором наборе входных данных валидные последовательности — это $$$[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]$$$. Вес $$$[0, 1]$$$ равен $$$2$$$, а остальные — $$$1$$$, так что ответ равен $$$5 \cdot 1 + 1 \cdot 2 = 7$$$.