P6296 轮换式 加强版

[原题链接](https://www.luogu.com.cn/problem/P5084) 本题与原题的区别，只有模数和数据范围不同。

小奔发现，对于任意的 $n$ 个字母，他们构成的轮换式，都表示成 $n$ 个基本轮换式的线性和。 一元的基本轮换式：$a$； 二元：$a+b$，$ab$； 三元：$a+b+c$，$ab+ac+bc$，$abc$； 四元：$a+b+c+d$，$ab+ac+ad+bc+bd+cd$，$abc+abd+bcd$，$abcd$； ...... 已知 $n$ 个数的各个基本轮换式的值，求它们的 $m$ 次方和，答案对 $899678209$（$899678209 = 429 \times 2^{21} + 1$）取模。

第一行两个正整数 $n,m$，意义如题目描述。 接下来一行 $n$ 个正整数，第 $i$ 个为 $a_i$，表示 $n$ 元 $i$ 次基本轮换式的值。

输出一行一个整数，表示答案。

【样例一解释】 可以列出方程 $a+b = 9$，$ab = 18$，容易算出 $a^2+b^2 = 45$。 【数据范围】 - 对于 $20\%$ 的数据，$1\le n \le 1000$，$1\le m \le 10^4$； - 对于 $60\%$ 的数据，$1\le n \le 1000$，$1\le m \le 10^9$； - 对于 $100\%$ 的数据，$1\le n \le 3 \times 10^4$，$1\le m \le 10^9$，$1\le a_i \le 10^8$。