题目背景

原题链接

本题与原题的区别，只有模数和数据范围不同。

题目描述

小奔发现，对于任意的 $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$ 次基本轮换式的值。

输出格式

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

2 2
9 18

45

9 233333
9 1 8 7 5 6 3 4 2

100006329

提示

【样例一解释】
可以列出方程 $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$。