题目描述

给定一个正整数 $N$。通过以下步骤生成 $(1,2,\\cdots,3N)$ 的排列 $(P_1,P_2,\\cdots,P_{3N})$。由于结果可能非常大，所以对质数 $M$ 取模后输出。

• 使用整数 $1$ 到 $3N$ 恰好一次，构造 $N$ 个长度为 $3$ 的序列 $A_1,A_2,\\cdots,A_N$。
• 构造一个空序列 $P$，并进行以下操作 $3N$ 次：
  • 从非空序列 $A_i$ 的开头选取最小的元素 $x$。
  • 将 $x$ 从序列中移除，并将 $x$ 添加到 $P$ 的末尾。

约束条件

• $1 \\leq N \\leq 2000$
• $10^8 \\leq M \\leq 10^9+7$
• $M$ 是一个质数。
• 输入中的所有值都是整数。

输入格式

输入格式如下：

$N$ $M$

输出格式

输出在模 $M$ 下的排列数。

示例输入 1

1 998244353

示例输出 1

6

计算所有长度为 $3$ 的排列数。

示例输入 2

2 998244353

示例输出 2

261

示例输入 3

314 1000000007

示例输出 3

182908545