CF1081G.Mergesort Strikes Back

Chouti thought about his very first days in competitive programming. When he had just learned to write merge sort, he thought that the merge sort is too slow, so he restricted the maximum depth of recursion and modified the merge sort to the following:

Chouti found his idea dumb since obviously, this "merge sort" sometimes cannot sort the array correctly. However, Chouti is now starting to think of how good this "merge sort" is. Particularly, Chouti wants to know for a random permutation $a$ of $1, 2, \ldots, n$ the expected number of inversions after calling MergeSort(a, 1, n, k).

It can be proved that the expected number is rational. For the given prime $q$, suppose the answer can be denoted by $\frac{u}{d}$ where $gcd(u,d)=1$, you need to output an integer $r$ satisfying $0 \le r \lt q$ and $rd \equiv u \pmod q$. It can be proved that such $r$ exists and is unique.

Chouti 回忆起自己刚接触算法竞赛时的时光。当他刚刚学会编写归并排序时，觉得归并排序太慢了，于是他限制了递归的最大深度，并将归并排序修改为如下形式：

Chouti 很快意识到自己的想法很愚蠢，因为显然这种“归并排序”有时无法正确地对数组排序。然而，Chouti 现在开始思考这种“归并排序”的性能究竟如何。特别地，Chouti 想知道：对于 $1, 2, \ldots, n$ 的一个随机排列 $a$，调用 MergeSort(a, 1, n, k) 后，数组中逆序对数量的期望值是多少。

可以证明该期望值是一个有理数。对于给定的质数 $q$，假设该答案可表示为 $\frac{u}{d}$，其中 $\gcd(u,d)=1$，你需要输出一个整数 $r$，满足 $0 \le r < q$ 且 $rd \equiv u \pmod q$。可以证明这样的 $r$ 存在且唯一。

The first and only line contains three integers $n, k, q$ ($1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$, $q$ is a prime).

第一行且唯一一行包含三个整数 $n, k, q$（$1 \leq n, k \leq 10^5$，$10^8 \leq q \leq 10^9$，$q$ 为质数）。

The first and only line contains an integer $r$.

第一行且唯一一行包含一个整数 $r$。

In the first example, all possible permutations are $[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$.

With $k=1$, MergeSort(a, 1, n, k) will only return the original permutation. Thus the answer is $9/6=3/2$, and you should output $499122178$ because $499122178 \times 2 \equiv 3 \pmod {998244353}$.

In the second example, all possible permutations are $[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$ and the corresponding outputs of MergeSort(a, 1, n, k) are $[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$ respectively. Thus the answer is $4/6=2/3$, and you should output $665496236$ because $665496236 \times 3 \equiv 2 \pmod {998244353}$.

在第一个例子中，所有可能的排列为 $[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}$。