题目描述

正整数 $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$ で割ったあまりを出力せよ。

题目大意

• 给定如下构造生成长度为 $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$。

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$ の順列が条件を満たします。