← 返回题目列表

Codeforces · 1768/E

E. 部分排序

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

考虑长度为 $$$3n$$$ 的排列$$$^\dagger$$$ $$$p$$$。每次可以执行以下操作之一:

- 按升序对前 $$$2n$$$ 元素进行排序。
- 按升序对最后 $$$2n$$$ 元素进行排序。

我们可以证明,仅使用这些操作就可以按升序对每个排列进行排序。我们将 $$$f(p)$$$ 称为使排列 $$$p$$$ 按升序排序所需的最少操作数。

给定 $$$n$$$,求 $$$f(p)$$$ 在所有 $$$(3n)!$$$ 排列 $$$p$$$ 上的总和,大小为 $$$3n$$$。

由于答案可能非常大,因此输出它对素数 $$$M$$$ 取模。

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成,顺序任意。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

输入的唯一行包含两个数字 $$$n$$$ 和 $$$M$$$ ($$$1 \leq n \leq 10^6$$$, $$$10^8 \leq M \leq 10^9$$$)。保证 $$$M$$$ 是素数。

输出

输出对 $$$M$$$ 取模的答案。

示例

输入 #1

1 100009067

输出 #1

9

输入 #2

2 100000357

输出 #2

1689

输入 #3

69 999900997

输出 #3

193862705

注意

在第一个测试用例中,所有排列都是:

- $$$[1, 2, 3]$$$,需要 $$$0$$$ 操作;
- $$$[1, 3, 2]$$$,需要$$$1$$$操作;
- $$$[2, 1, 3]$$$,需要$$$1$$$操作;
- $$$[2, 3, 1]$$$,需要 $$$2$$$ 操作;
- $$$[3, 1, 2]$$$,需要 $$$2$$$ 操作;
- $$$[3, 2, 1]$$$,需要 $$$3$$$ 操作。

因此,答案是$$$0+1+1+2+2+3=9$$$。