配点 : $1200$ 点

問題文

正整数 $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$ を追加する。
• 各数列 $A_i$ のうち、空でないものの先頭の要素を見て、そのうち最小の要素を $x$ とする。
• $x$ を $A_i$ から消去する。 $P$ の最後尾に $x$ を追加する。

制約

• $1 \leq N \leq 2000$
• $10^8 \leq M \leq 10^9+7$
• $M$ は素数
• 入力はすべて整数

入力

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

$N$ $M$

出力

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

1 998244353

6

すべての長さ $3$ の順列が条件を満たします。

2 998244353

261

314 1000000007

182908545