题目描述

给你一个正整数 $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

输入 #1

1 998244353

输出 #1

6

输入输出样例 #2

输入 #2

2 998244353

输出 #2

261

输入输出样例 #3

输入 #3

314 1000000007

输出 #3

182908545

说明/提示

样例 1 解释

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