Description

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:

Output the answer modulo $p$.

Input Format

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 Format

Output one integer in one line, representing the answer.

6 233 42
1 4 2 8 5 7

91

Hint

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