CF1768E.Partial Sorting

Consider a permutation$^\dagger$ $p$ of length $3n$. Each time you can do one of the following operations:

• Sort the first $2n$ elements in increasing order.
• Sort the last $2n$ elements in increasing order.

We can show that every permutation can be made sorted in increasing order using only these operations. Let's call $f(p)$ the minimum number of these operations needed to make the permutation $p$ sorted in increasing order.

Given $n$, find the sum of $f(p)$ over all $(3n)!$ permutations $p$ of size $3n$.

Since the answer could be very large, output it modulo a prime $M$.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

考虑一个长度为 $3n$ 的排列$^\dagger$ $p$。每次你可以执行以下两种操作之一：

• 将前 $2n$ 个元素按升序排序；
• 将后 $2n$ 个元素按升序排序。

可以证明：仅使用这两种操作，任意排列 $p$ 均可被变为升序排列。记 $f(p)$ 为将排列 $p$ 变为升序排列所需的最少操作次数。

给定 $n$，求所有 $(3n)!$ 个长度为 $3n$ 的排列 $p$ 对应的 $f(p)$ 之和。

由于答案可能非常大，请对一个给定质数 $M$ 取模后输出。

$^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

The only line of input contains two numbers $n$ and $M$ ($1 \leq n \leq 10^6$, $10^8 \leq M \leq 10^9$). It is guaranteed that $M$ is a prime number.

输入仅包含一行，其中有两个数 $n$ 和 $M$（$1 \leq n \leq 10^6$，$10^8 \leq M \leq 10^9$）。保证 $M$ 是一个质数。

Output the answer modulo $M$.

输出答案对 $M$ 取模的结果。

In the first test case, all the permutations are:

• $[1, 2, 3]$, which requires $0$ operations;
• $[1, 3, 2]$, which requires $1$ operation;
• $[2, 1, 3]$, which requires $1$ operation;
• $[2, 3, 1]$, which requires $2$ operations;
• $[3, 1, 2]$, which requires $2$ operations;
• $[3, 2, 1]$, which requires $3$ operations.

Therefore, the answer is $0+1+1+2+2+3=9$.

在第一个测试用例中，所有排列如下：

• $[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$。