P6296 Rotational Form (Enhanced Version)

[Original problem link](https://www.luogu.com.cn/problem/P5084) The only differences between this problem and the original one are the modulus and the Constraints.

Xiao Ben found that for any $n$ letters, the rotational form they form can be expressed as a linear combination of $n$ basic rotational forms. Unary basic rotational form: $a$; Binary: $a+b$, $ab$; Ternary: $a+b+c$, $ab+ac+bc$, $abc$; Quaternary: $a+b+c+d$, $ab+ac+ad+bc+bd+cd$, $abc+abd+bcd$, $abcd$; ...... Given the values of all basic rotational forms of $n$ numbers, find the sum of their $m$-th powers. Output the answer modulo $899678209$ ($899678209 = 429 \times 2^{21} + 1$).

The first line contains two positive integers $n, m$, with meanings as described in the statement. The next line contains $n$ positive integers. The $i$-th number is $a_i$, representing the value of the $i$-th basic rotational form of $n$ variables.

Output one integer in one line, representing the answer.

[Explanation for Sample 1] We can write the equations $a+b = 9$ and $ab = 18$, and it is easy to compute $a^2+b^2 = 45$. [Constraints] - For $20\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10^4$; - For $60\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10^9$; - For $100\%$ of the testdata, $1 \le n \le 3 \times 10^4$, $1 \le m \le 10^9$, $1 \le a_i \le 10^8$. Translated by ChatGPT 5