轮换式

小奔发现，对于任意的 $n$ 个字母，他们构成的轮换式，都表示成 $n$ 个基本 $1\sim n$ 次基本轮换式的线性和。 一元的基本轮换式：$a$； 二元：$a+b,ab$； 三元：$a+b+c,ab+ac+bc,abc$； 四元：$a+b+c+d,ab+ac+bc+ad+bd+cd,abc+abd+acd+bcd,abcd$； ……………… 同样的，对于任意的 $n$ 个字母，给出他们的几个基本轮换式，都可以求出这几个字母的值。 但是小奔突然大发慈悲，他只需要你求出这些字母的 $m$ 次方和模 $10^7+29$ 的值。

第一行是字母个数 $n$ ，次数 $m$ 。 接下来一行 $n$ 个正整数，第 $i$ 个为 $a_i$ $(0<a_i\le 10000)$，从左到右分别是 $1\sim n$ 次 $n$ 元基本轮换式的值。

一个数，要求的答案。

2 2
9 18

45

本题共有 $3$ 个子任务。 Subtask 1（12 pts）：$n\le 2$； Subtask 2（28 pts）：$n=3$； Subtask 3（60 pts）：$n=4$。 对于所有数据，$0\le m\le 100000$。