P5084 Rotational Form

Xiao Ben found that, for any $n$ letters, the “rotational form” they form can always be expressed as a linear combination of the $n$ basic rotational forms of degrees $1 \sim n$. Unary basic rotational form: $a$. Binary: $a+b,ab$. Ternary: $a+b+c,ab+ac+bc,abc$. Quaternary: $a+b+c+d,ab+ac+bc+ad+bd+cd,abc+abd+acd+bcd,abcd$. And so on. Similarly, for any $n$ letters, if you are given several of their basic rotational forms, you can determine the values of these letters. However, Xiao Ben suddenly showed mercy: he only asks you to compute the sum of the $m$-th powers of these letters modulo $10^7+29$.

The first line contains the number of letters $n$ and the exponent $m$. The next line contains $n$ positive integers. The $i$-th number is $a_i$ $(0

Output one number, the required answer.

This problem has $3$ subtasks. Subtask 1 (12 pts): $n\le 2$. Subtask 2 (28 pts): $n=3$. Subtask 3 (60 pts): $n=4$. For all data, $0\le m\le 100000$. Translated by ChatGPT 5