Power Sum from Elementary Symmetric Sums

Given n numbers, consider their elementary symmetric sums as follows:

• For one variable: \(a\)
• For two variables: \(a+b\) and \(ab\)
• For three variables: \(a+b+c\), \(ab+ac+bc\), and \(abc\)
• For four variables: \(a+b+c+d\), \(ab+ac+ad+bc+bd+cd\), \(abc+abd+bcd\) and \(abcd\)
• \(\ldots\)

It is known that any symmetric function of these numbers (in particular the sum of their m-th powers) can be expressed as a linear recurrence in the n elementary symmetric sums. More precisely, if the elementary symmetric sums are \(e_1, e_2, \ldots, e_n\), then the power sums defined as \(P_m = \sum_{i=1}^{n} a_i^m\) satisfy the Newton's identities. For \(1 \le m \le n\) we have:

[ P_m = e_1 P_{m-1} - e_2 P_{m-2} + \cdots + (-1)^{m-1} m,e_m, ]

and for \(m > n\) the recurrence becomes:

[ P_m = e_1 P_{m-1} - e_2 P_{m-2} + \cdots + (-1)^{n-1} e_n P_{m-n}. ]

Your task is: Given the integers n and m along with the n elementary symmetric sums \(e_1, e_2, \ldots, e_n\), compute the value of \(P_m = \sum_{i=1}^{n} a_i^m\) modulo \(899678209\) (where \(899678209 = 429\times 2^{21}+1\)).

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(m \ge 0\)). The second line contains \(n\) integers \(e_1, e_2, \ldots, e_n\), which are the elementary symmetric sums modulo \(899678209\).

outputFormat

Output a single integer: \(P_m\) modulo \(899678209\).

sample

1 5
3

243