[AGC043D] Merge Triplets

- 给定如下构造生成长度为 $3N$ 的排列 $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$。

[problemUrl]: https://atcoder.jp/contests/agc043/tasks/agc043_d 正整数 $ N $ が与えられます。 $ (1,2,\cdots,3N) $ の順列 $ (P_1,P_2,\cdots,P_{3N}) $であって、次の操作によって生成されうるものの数を求めてください。 ただし、答えは非常に大きくなることがあるので、素数 $ M $ で割ったあまりを求めてください。 - 長さ $ 3 $ の数列を $ N $ 個用意する。この数列たちを $ A_1,A_2,\cdots\ ,A_N $ とする。この $ 3N $ 個の値には $ 1 $ から $ 3N $ がちょうど一度ずつ登場せねばならない。 - 空の数列 $ P $ を用意する。以下の操作を $ 3N $ 回繰り返す。 - 各数列 $ A_i $ のうち、空でないものの先頭の要素を見て、そのうち最小の要素を $ x $ とする。 - $ x $ を $ A_i $ から消去する。 $ P $ の最後尾に $ x $ を追加する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

条件を満たす順列の数を $ M $ で割ったあまりを出力せよ。

1 998244353

6

2 998244353

261

314 1000000007

182908545

### 制約 - $ 1\ \leq\ N\ \leq\ 2000 $ - $ 10^8\ \leq\ M\ \leq\ 10^9+7 $ - $ M $ は素数 - 入力はすべて整数 ### Sample Explanation 1 すべての長さ $ 3 $ の順列が条件を満たします。