考虑长度为 $$$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$$$。