E. Частичная сортировка
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим перестановку$$$^\dagger$$$ $$$p$$$ длины $$$3n$$$. За один шаг вы можете выполнить одну из следующих операций:

  • Отсортировать первые $$$2n$$$ элементов в возрастающем порядке.
  • Отсортировать последние $$$2n$$$ элементов в возрастающем порядке.

Можно показать, что любую перестановку можно отсортировать по возрастанию, используя только эти операции. Пусть $$$f(p)$$$ — минимальное количество операций, необходимых для сортировки перестановки $$$p$$$ в возрастающем порядке.

По данному $$$n$$$ найдите сумму $$$f(p)$$$ по всем $$$(3n)!$$$ перестановкам $$$p$$$ длины $$$3n$$$.

Так как ответ может быть очень большим, выведите его по модулю простого числа $$$M$$$.

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

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

Единственная строка ввода содержит два числа $$$n$$$ и $$$M$$$ ($$$1 \leq n \leq 10^6$$$, $$$10^8 \leq M \leq 10^9$$$). Гарантируется, что $$$M$$$ — простое число.

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

Выведите ответ по модулю $$$M$$$.

Примеры
Входные данные
1 100009067
Выходные данные
9
Входные данные
2 100000357
Выходные данные
1689
Входные данные
69 999900997
Выходные данные
193862705
Примечание

В первом примере считается сумма по данным перестановкам:

  • $$$[1, 2, 3]$$$ требует $$$0$$$ операций;
  • $$$[1, 3, 2]$$$ требует $$$1$$$ операцию;
  • $$$[2, 1, 3]$$$ требует $$$1$$$ операцию;
  • $$$[2, 3, 1]$$$ требует $$$2$$$ операции;
  • $$$[3, 1, 2]$$$ требует $$$2$$$ операции;
  • $$$[3, 2, 1]$$$ требует $$$3$$$ операции.

Таким образом, ответ $$$0+1+1+2+2+3=9$$$.