Some person is given a bag consisting of N distinct balls, represented by an array A of size N, where the $i^{th}$ ball has integer $A_{i}$ written on it. Now, a game is played, where a player picks a ball from the bag K times, with repetition allowed.

He (the player) then notes the product of all numbers written on the balls picked, Soon, though he realizes that the number formed is too big, so he only considers the product Mod a given prime P. Let's call the product of the integers written on the picked balls Mod P as Z.

Considering that the probability of picking each ball is the same for each of the K picks, you need to find the Expected Value of Z. Let the answer be an irreducible fraction $X/Y$. You need to find and print $X \cdot Y^{-1}$ Mod $998244353$.

Input Format:

The first line consists of 3 space separated integers N ,P and K. The next line consists of N space separated integers , where the $i^{th}$ integer represents $A_{i}$

Output Format :

Print the expected value of Z.

Constraints :

$1 \le N \le 100,000$

$3 \le P \le 50,000$

$1 \le A_{i} < P$

$1 \le K \le 10,000,000$

P is prime.

It can be proved, that for the following constraints $Y^{-1}$ Mod $998244353$ always exists.