轮换式
题目描述
小奔发现,对于任意的 $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$ 元基本轮换式的值。
输出格式
一个数,要求的答案。
输入输出样例
输入样例 #1
2 2
9 18
输出样例 #1
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$。