Problem Description

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

Input Format

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<a_i\le 10000)$, which from left to right are the values of the $n$-variable basic rotational forms of degrees $1 \sim n$.

Output Format

Output one number, the required answer.

2 2
9 18

45

Hint

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