回想一下,排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
序列 $$$a$$$ 是序列 $$$b$$$ 的子段,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。我们将子段表示为 $$$[l, r]$$$,其中 $$$l, r$$$ 是两个整数,$$$1 \le l \le r \le n$$$。这表示从序列中删除开头的 $$$l-1$$$ 元素和结尾的 $$$n-r$$$ 元素的子段。
对于排列 $$$p_1, p_2, \ldots, p_n$$$,我们将框架段定义为子段 $$$[l,r]$$$,其中 $$$\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$$$。例如,对于排列 $$$(6, 7, 1, 8, 5, 3, 2, 4)$$$,其一些框架段是:$$$[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$$$。特别是,子段 $$$[i,i]$$$ 始终是 $$$1$$$ 和 $$$n$$$(含)之间的任何 $$$i$$$ 的框架段。
我们将排列$$$p$$$的幸福度定义为$$$(l, r)$$$对的数量,使得$$$1 \le l \le r \le n$$$,并且$$$[l, r]$$$是一个框架段。例如,排列 $$$[3, 1, 2]$$$ 的幸福度为 $$$5$$$:除了 $$$[1, 2]$$$ 之外的所有段都是框架段。
给定整数 $$$n$$$ 和 $$$m$$$,Jongwon 想要计算长度为 $$$n$$$ 的所有排列的幸福感之和,并对质数 $$$m$$$ 取模。请注意,存在 $$$n!$$$($$$n$$$ 的阶乘)长度为 $$$n$$$ 的不同排列。
输入
唯一的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 250\,000$$$,$$$10^8 \le m \le 10^9$$$,$$$m$$$ 是质数)。
输出
打印 $$$r$$$ ($$$0 \le r < m$$$),长度为 $$$n$$$ 的所有排列的幸福感之和,以质数 $$$m$$$ 为模。
示例
输入 #1
1 993244853
输出 #1
1
输入 #2
2 993244853
输出 #2
6
输入 #3
3 993244853
输出 #3
32
输入#4
2019 993244853
输出#4
923958830
输入 #5
2020 437122297
输出 #5
265955509
注意
对于样本输入 $$$n=3$$$,让我们考虑长度为 $$$3$$$ 的所有排列:
- $$$[1, 2, 3]$$$,所有子段都是框架段。幸福是$$$6$$$。
- $$$[1, 3, 2]$$$,除 $$$[1, 2]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[2, 1, 3]$$$,除 $$$[2, 3]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[2, 3, 1]$$$,除 $$$[2, 3]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[3, 1, 2]$$$,除 $$$[1, 2]$$$ 之外的所有子段都是框架段。幸福是$$$5$$$。
- $$$[3, 2, 1]$$$,所有子段都是框架段。幸福是$$$6$$$。
因此,幸福感的总和是$$$6+5+5+5+5+6 = 32$$$。