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). 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 < p < 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). 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}