Modular Polynomial Combinatorics

Given three integers \( n \), \( x \), and \( p \), and a polynomial of degree \( m \) defined as \( f(k)=a_{0}+a_{1}k+a_{2}k^2+\cdots+a_{m}k^m \), compute the following expression modulo \( p \):

$$ S = \left( \sum_{k=0}^{n} f(k)\times x^k\times \binom{n}{k} \right) \bmod p. $$

Here, the binomial coefficient is defined as \( \binom{n}{k} = \frac{n!}{k!(n-k)!} \). You are to output the value of \( S \).

inputFormat

The input consists of two lines:

• The first line contains three space-separated integers \( n \), \( x \), and \( p \).
• The second line begins with an integer \( m \) (the degree of the polynomial) followed by \( m+1 \) space-separated integers: \( a_{0}, a_{1}, \dots, a_{m} \), which are the coefficients of \( f(k) \) in increasing order of degree.

outputFormat

Output a single integer representing \( S = \left( \sum_{k=0}^{n} f(k)\times x^k\times \binom{n}{k} \right) \bmod p \).

sample

3 2 100
1 1 1

81