AT_agc043_d.[AGC043D] Merge Triplets

给你一个正整数 $N$，计算可以按以下方法生成的 $1$ 到 $3N$ 的排列 $(P_1,P_2,\cdots,P_{3N})$ 的个数。

答案可以很大，所以你需要输出它对一个质数 $M$ 取模的值。

• 构造 $N$ 个长度为 $3$ 的序列 $A_1,A_2,\cdots,A_N$，其中 $1$ 到 $3N$ 每个数字均恰好出现一次。
• $P$ 初始为空，重复以下操作 $3N$ 次：
  • 对于所有的非空序列 $A_i$，令 $x$ 为它们的第一个元素中最小的一个。
  • 在 $x$ 所在的 $A_i$ 中删除 $x$，然后把 $x$ 加入 $P$ 的末尾。

一行两个整数 $N,M$（$1\le N\le 2000,10^8\le M\le 10^9+7$，$M$ 为质数）。

输出一行一个整数，表示答案对 $M$ 取模后的值。

样例 1 解释

所有长度为 $3$ 的排列均满足条件。