[agc043_d]Merge Triplets

ID: 1961

传统题

6000ms

1024MiB

难度: 8

上传者:

标签>

2700+

给定如下构造生成长度为 $3N$ $3 N$ 的排列 $P$ $P$ 的方法：
- 先生成一个长度为 $3N$ 的排列 $A$ 。然后将 $\forall k \in [0, N-1]$ ， $A_{3k+1},A_{3k+2},A_{3k+3}$ 分成一块。
- 有 $N$ 个指针，初始指向每个块的第一个数。
- 每次选择所有指针指向的数中最小的数删除，然后放到 $P$ 的末尾。之后指向被删除的数后移一个位置。若移出块了，则删除这个指针。
请你求出，一共能生成长度为 $3N$ 的排列共多少种。答案可能很大，请求出对 $M$ 取模的结果。
$1 \leq N \leq 2 \times 10^3$ ， $10^8\leq M \leq 10^9+7$ 。

#agc043d. [agc043_d]Merge Triplets