P5431 [Template] Multiplicative Inverse Modulo 2

Given $n$ positive integers $a_i$, find their multiplicative inverses modulo $p$. Since outputting all inverses would be too much, a constant $k$ is given. The answer you need to output is: $$\sum\limits_{i=1}^n\frac{k^i}{a_i}$$ Output the answer modulo $p$.

The first line contains three positive integers $n, p, k$, with the meaning as described in the statement. The second line contains $n$ positive integers $a_i$, the numbers whose inverses you need to compute.

Output one integer in one line, representing the answer.

For $30\%$ of the testdata, $1 \le n \le 10^5$. For $100\%$ of the testdata, $1 \le n \le 5\times 10^6$, $2 \le k < p \le 10^9$, $1 \le a_i < p$, and $p$ is guaranteed to be prime. Note: The time limit for this problem is relatively strict. Please use faster I/O methods. Translated by ChatGPT 5