← 返回题目列表

AtCoder · agc043_d

D. 合并三元组

中文机器翻译题面 查看原题

分数: 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