C. Новый год и перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Напомним, что перестановкой является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Последовательность $$$a$$$ является подотрезком $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца. Обозначим подотрезок как $$$[l, r]$$$, где $$$l, r$$$ — целые числа и $$$1 \le l \le r \le n$$$. Это обозначает подотрезок, у которого убрали $$$l-1$$$ элементов слева и $$$n-r$$$ справа.

Для перестановки $$$p_1, p_2, \ldots, p_n$$$ назовём рамочным подотрезком такой подотрезок индексов $$$[l,r]$$$, в котором $$$\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$$$. Например, у перестановки $$$(6, 7, 1, 8, 5, 3, 2, 4)$$$ некоторые из рамочных подотрезков: $$$[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$$$. В частности, подотрезок $$$[i,i]$$$ всегда является рамочным подотрезком для любого $$$i$$$ от $$$1$$$ до $$$n$$$ включительно.

Для перестановки $$$p$$$ определим счастье перестановки как количество таких пар $$$(l, r)$$$, что $$$1 \le l \le r \le n$$$ и $$$[l, r]$$$ является рамочным подотрезком. Например, перестановка $$$[3, 1, 2]$$$ имеет счастье $$$5$$$: Все подотрезки индексов кроме $$$[1, 2]$$$ являются рамочными.

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

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

Входные данные содержат два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 250\,000$$$, $$$10^8 \le m \le 10^9$$$, $$$m$$$ — простое).

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

Выведите $$$r$$$ ($$$0 \le r < m$$$) — суммарное счастье всех перестановок длины $$$n$$$ по модулю простого числа $$$m$$$.

Примеры
Входные данные
1 993244853
Выходные данные
1
Входные данные
2 993244853
Выходные данные
6
Входные данные
3 993244853
Выходные данные
32
Входные данные
2019 993244853
Выходные данные
923958830
Входные данные
2020 437122297
Выходные данные
265955509
Примечание

Пусть $$$n=3$$$, тогда рассмотрим все перестановки длиной $$$3$$$:

  • $$$[1, 2, 3]$$$, все подотрезки являются рамочными подотрезками. Счастье равно $$$6$$$.
  • $$$[1, 3, 2]$$$, все подотрезки, кроме $$$[1, 2]$$$, являются рамочными подотрезками. Счастье равно $$$5$$$.
  • $$$[2, 1, 3]$$$, все подотрезки, кроме $$$[2, 3]$$$, являются рамочными подотрезками. Счастье равно $$$5$$$.
  • $$$[2, 3, 1]$$$, все подотрезки, кроме $$$[2, 3]$$$, являются рамочными подотрезками. Счастье равно $$$5$$$.
  • $$$[3, 1, 2]$$$, все подотрезки, кроме $$$[1, 2]$$$, являются рамочными подотрезками. Счастье равно $$$5$$$.
  • $$$[3, 2, 1]$$$, все подотрезки являются рамочными подотрезками. Счастье равно $$$6$$$.

Поэтому суммарное счастье равно $$$6+5+5+5+5+6 = 32$$$.