题目描述

小奔发现，对于任意的 $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$。