C2. Красивые узоры (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 2 \cdot 10^5$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Попав в старинный дворец «Палиндром-Палас», Вы заметили, что на его стенах есть диковинные узоры. Узор представляет собой мозаику размера $$$1 \times n$$$ из камушков, каждый из которых покрашен в один из $$$m$$$ различных цветов.

Правильностью произвольной мозаики $$$s$$$ назовём количество непустых подотрезков $$$s$$$, которые являются палиндромами. Красотой мозаики назовём квадрат её правильности. Например, у мозаики rgrb — пять подотрезков-палиндромов: r, g, r, b и rgr. Поэтому её правильность равна $$$5$$$, а красота $$$25$$$.

Гуляя по этому дворцу, вы задались вопросом: чему равно математическое ожидание красоты мозаики, если цвет каждого из $$$n$$$ камушков выбирается равновероятно и независимо от цветов остальных камней. Выведите ответ по модулю $$$p$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит 3 целых числа $$$n$$$, $$$m$$$ и $$$p$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq m \leq 10^7$$$; $$$m \lt p \lt 10^9$$$) длину мозаики, количество различных цветов камушков и модуль, по которому необходимо вычислить ответ.

Гарантируется, что $$$p$$$ — простое число. Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите в отдельной строке единственное целое число: математическое ожидание красоты мозаики по модулю $$$p$$$.

Формально, пусть $$$x = p$$$. Можно показать, что точный ответ может быть представлен в виде несократимой дроби $$$\frac{y}{z}$$$, где $$$y$$$ и $$$z$$$ — целые числа, и $$$z \not \equiv 0 \pmod{x}$$$. Выведите целое число, равное $$$y \cdot z^{-1} \bmod x$$$. Другими словами, выведите такое целое число $$$t$$$, что $$$0 \le t \lt x$$$ и $$$t \cdot z \equiv y \pmod{x}$$$.

Пример
Входные данные
3
2 2 101
5 1 999999937
100 23190 3214373
Выходные данные
57
225
2347147
Примечание

В первом примере всего существует четыре мозаики длины $$$2$$$, если для их постройки можно использовать камушки лишь двух различных цветов, в двух из них по два подотрезка-палиндрома, а в двух других — по три. Получается, что математическое ожидание красоты мозаики равняется $$$\left(\frac{2^2}{4} + \frac{2^2}{4} + \frac{3^2}{4} + \frac{3^2}{4}\right) = 13 \cdot 2^{-1} \bmod 101 = 57$$$.

Во втором примере все подотрезки мозаики длины 5 будут являться палиндромами.