CF2174C2.Beautiful Patterns (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $n \le 2 \cdot 10^5$. You can hack only if you solved all versions of this problem.

Upon entering the ancient palace "Palindrome-Palace", you noticed that there are peculiar patterns on its walls. The pattern is a mosaic of size $1 \times n$ made of pebbles, each painted in one of $m$ different colors.

The correctness of an arbitrary mosaic $s$ is defined as the number of non-empty subsegments of $s$ that are palindromes. The beauty of the mosaic is defined as the square of its correctness. For example, for the mosaic rgrb, there are five palindromic subsegments: r, g, r, b, and rgr. Therefore, its correctness is $5$, and its beauty is $25$.

While wandering through this palace, you wondered: what is the expected value of the beauty of the mosaic if the color of each of the $n$ pebbles is chosen uniformly and independently of the colors of the other pebbles? Print the answer modulo prime $p$.

这是该问题的困难版本。两个版本的区别在于，在本版本中，$n \le 2 \cdot 10^5$。仅当您已解决该问题的所有版本时，才可进行 Hack。

当你进入古老的宫殿“回文宫”（Palindrome-Palace）时，你注意到其墙壁上有着奇特的图案。该图案是一条 $1 \times n$ 规格的镶嵌画，由鹅卵石拼成，每颗鹅卵石被涂成 $m$ 种不同颜色之一。

任意镶嵌画 $s$ 的正确性（correctness）定义为 $s$ 中非空回文子段（subsegment）的个数；其美感（beauty）则定义为正确性的平方。例如，对于镶嵌画 rgrb，共有五个回文子段：r、g、r、b 和 rgr。因此其正确性为 $5$，美感为 $25$。

当你在这座宫殿中漫游时，你不禁思考：若 $n$ 颗鹅卵石各自的颜色均独立且均匀地从 $m$ 种颜色中随机选取，则该镶嵌画的美感的期望值是多少？请输出答案对素数 $p$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The only line of each test case contains 3 integers $n$, $m$, and $p$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq m \leq 10^7$; $m \lt p \lt 10^9$) representing the length of the mosaic, the number of different colors of pebbles, and the modulus for which the answer needs to be computed.

It is guaranteed that $p$ is a prime number. It is also guaranteed that the sum of $n$ across all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含三个整数 $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$。

For each test case, output the expected beauty of the mosaic modulo $p$.

Formally, let $x = p$. It can be shown that the exact answer can be expressed as an irreducible fraction $\frac{y}{z}$, where $y$ and $z$ are integers and $z \not \equiv 0 \pmod{x}$. Output the integer equal to $y \cdot z^{-1} \bmod x$. In other words, output such an integer $t$ that $0 \le t \lt x$ and $t \cdot z \equiv y \pmod{x}$.

对每个测试用例，输出马赛克的期望美观度对 $p$ 取模的结果。

形式化地，令 $x = p$。可以证明，精确答案可表示为既约分数 $\frac{y}{z}$，其中 $y$ 和 $z$ 为整数，且 $z \not \equiv 0 \pmod{x}$。请输出满足 $y \cdot z^{-1} \bmod x$ 的整数。换言之，输出满足 $0 \le t \lt x$ 且 $t \cdot z \equiv y \pmod{x}$ 的整数 $t$。

In the first test case, there are a total of four mosaics of length $2$ if only two different colors of pebbles can be used to construct them, with two of them having two palindromic subsegments, and the other two having three each. Thus, the expected value of the beauty of the mosaic is $\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$.

In the second test case, all subsegments of the mosaic of length 5 will be palindromes.

在第一个测试用例中，若仅使用两种不同颜色的卵石来构造，长度为 $2$ 的马赛克共有 $4$ 种，其中两种各有 $2$ 个回文子段，其余两种各有 $3$ 个回文子段。因此，该马赛克美观度的期望值为 $\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$ 的马赛克的所有子段均为回文。