G. Сортировка слиянием наносит ответный удар
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Chouti вспомнил о его первых днях в спортивном программировании. Когда он только научился писать сортировку слиянием, он подумал, что сортировка слиянием слишком медленная, поэтому он ограничил максимальную глубину рекурсии и модифицировал алгоритм следующим образом:

Chouti нашёл свою идею глупой, потому что, очевидно, эта «сортировка слиянием» иногда не может отсортировать массив правильно. Тем не менее, Chouti теперь хочет оценить, насколько его «сортировка слиянием» хороша. В частности, Chouti хочет узнать для случайной перестановки $$$a$$$ чисел $$$1, 2, \ldots, n$$$ математичекое ожидание числа инверсий после вызова MergeSort(a, 1, n, k).

Можно доказать, что математическое ожидание рационально. Для заданного простого числа $$$q$$$ допустим, что ответ может быть представлен как $$$\frac{u}{d}$$$ где $$$gcd(u,d)=1$$$. Выведите целое число $$$r$$$ удовлетворяющее $$$0 \le r<q$$$ и $$$rd \equiv u \pmod q$$$. Можно доказать, что такое $$$r$$$ существует и уникально.

Входные данные

В единственной строке записаны три целых числа $$$n, k, q$$$ ($$$1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$$$, $$$q$$$ — простое).

Выходные данные

В единственной строке выведите число $$$r$$$.

Примеры
Входные данные
3 1 998244353
Выходные данные
499122178
Входные данные
3 2 998244353
Выходные данные
665496236
Входные данные
9 3 998244353
Выходные данные
449209967
Входные данные
9 4 998244353
Выходные данные
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}$$$.