分数: 1200 点
问题陈述
给定的是一个正整数 N。 求排列数 (P_1,P_2,\cdots,P_{3N}) of (1,2,\cdots,3N) 。 这个数字可能很大,所以打印它对素数取模 M.
- 使 N 序列 A_1,A_2,\cdots,A_N 长度 3 每个,使用每个整数 1 通过 3N 恰好一次。
- 让 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