Modular Inverse Summation

Given n positive integers \(a_i\), compute the sum

\(\displaystyle \sum\limits_{i=1}^{n}\frac{k^i}{a_i} \mod p\)

where \(\frac{1}{a_i}\) denotes the modular multiplicative inverse of \(a_i\) modulo \(p\) (which is guaranteed to exist since \(p\) is prime and \(a_i \not\equiv 0 \pmod{p}\)).

inputFormat

The first line contains three integers (n), (k), and (p) (with (p) being a prime number). The second line contains (n) positive integers (a_1, a_2, \dots, a_n).

outputFormat

Output a single integer: (\left(\sum\limits_{i=1}^{n}\frac{k^i}{a_i}\right) \mod p).

sample

3 2 7
1 2 3

2