Computing Power Sum from Elementary Symmetric Sums

Xiao Ben discovered an interesting algebraic fact: for any set of ( n ) letters (a_1, a_2, \dots, a_n), the set of all cyclic permutations (i.e. the basic cyclic sums) can be expressed as a linear combination of the ( n ) basic cyclic sums of orders (1) to (n). For example, when (n=1), the basic cyclic sum is (a_1); for (n=2), they are (a_1+a_2) and (a_1a_2); for (n=3), they are (a_1+a_2+a_3), (a_1a_2+a_1a_3+a_2a_3) and (a_1a_2a_3); and so on.

Given the (n) elementary symmetric sums (e_1, e_2, \dots, e_n) of letters (a_1, a_2, \dots, a_n) (where (e_1 = a_1+a_2+\cdots+a_n), (e_2 = \sum_{1\le i<j\le n}a_ia_j), ..., (e_n = a_1a_2\cdots a_n)), one can uniquely determine the values of (a_i) by solving the corresponding system. However, Xiao Ben only cares about the sum of the (m)th powers of these letters, i.e., [ p_m = a_1^m + a_2^m + \cdots + a_n^m \mod (10^7+29), ] where all computations are done modulo (10^7+29).

You are given the integers (n) and (m), followed by (n) integers representing (e_1, e_2, \dots, e_n). Using Newton's identities, note that for ( k \geq 1 ) the power sums (p_k = a_1^k+\cdots+a_n^k) satisfy: [ \begin{aligned} p_k &= e_1 p_{k-1} - e_2 p_{k-2} + \cdots + (-1)^{k-1} k,e_k, \quad\text{for } 1 \le k \le n,\ p_k &= e_1 p_{k-1} - e_2 p_{k-2} + \cdots + (-1)^n e_n p_{k-n}, \quad\text{for } k > n. \end{aligned} ] When (m \le n) you can directly compute (p_m) using the above formula. When (m > n), use the recurrence relation along with matrix exponentiation to compute (p_m) efficiently. Your task is to output (p_m \mod (10^7+29)).

inputFormat

The first line of input contains two integers (n) and (m) (with (1 \le n \le \text{a reasonable bound}) and (m \ge 1)). The second line contains (n) integers (e_1, e_2, \dots, e_n) representing the elementary symmetric sums of (a_1, a_2, \dots, a_n).

outputFormat

Output a single integer, the value of (a_1^m+a_2^m+\cdots+a_n^m) modulo (10^7+29).

sample

1 3
2

8