Background

Original problem link

The only differences between this problem and the original one are the modulus and the Constraints.

Problem Description

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$).

Input Format

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 Format

Output one integer in one line, representing the answer.

2 2
9 18

45

9 233333
9 1 8 7 5 6 3 4 2

100006329

Hint

[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