Couti 回想起他刚开始参加竞争性编程的日子。当他刚学会写归并排序时,他认为归并排序太慢了,于是他限制了递归的最大深度,并将归并排序修改为如下:
Couti 发现他的想法很愚蠢,因为显然,这种“合并排序”有时无法正确对数组进行排序。然而,Chouti 现在开始思考这种“合并排序”有多好。特别是,Couti 想知道 $$$1, 2, \ldots, n$$$ 的随机排列 $$$a$$$ 调用 MergeSort(a, 1, n, k) 后的预期反转次数。
可以证明期望数是有理数。对于给定的素数 $$$q$$$,假设答案可以用 $$$\frac{u}{d}$$$ 表示,其中 $$$gcd(u,d)=1$$$,则需要输出满足 $$$0 \le r<q$$$ 和 $$$rd \equiv u \pmod q$$$ 的整数 $$$r$$$。可以证明这样的$$$r$$$存在并且是唯一的。
输入
第一行也是唯一一行包含三个整数 $$$n、k、q$$$($$$1 \leq n、k \leq 10^5、10^8 \leq q \leq 10^9$$$、$$$q$$$ 是质数)。
输出
第一行也是唯一一行包含一个整数 $$$r$$$。
示例
输入 #1
3 1 998244353
输出 #1
499122178
输入 #2
3 2 998244353
输出 #2
665496236
输入 #3
9 3 998244353
输出 #3
449209967
输入#4
9 4 998244353
输出#4
665496237
注意
在第一个示例中,所有可能的排列为 $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$。
当 $$$k=1$$$ 时,MergeSort(a, 1, n, k) 将仅返回原始排列。因此答案是 $$$9/6=3/2$$$,你应该输出 $$$499122178$$$ 因为 $$$499122178 \times 2 \equiv 3 \pmod {998244353}$$$。
在第二个示例中,所有可能的排列为 $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$,MergeSort(a, 1, n, k) 的相应输出为分别为$$$[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$$$。因此答案是$$$4/6=2/3$$$,你应该输出$$$665496236$$$,因为$$$665496236 \times 3 \equiv 2 \pmod {998244353}$$$。