Description

输入 $n$ 个正整数 $a_1,a_2...a_n$ 和一个正整数 $k$，求 ${a_1}^k+{a_2}^k+...+{a_n}^k$。

Format

Input

第一行：两个正整数 $n,k$，分别表示数据的个数和每一项的次数

第二行：$n$ 个正整数，表示多项式每一项的底数

Output

一个整数，表示多项式的值

Samples

3 2
1 2 3

14

4 4
12 34 56 78

48206624

Limitation

对于40%的数据，$1≤n,a_i≤50,0≤k≤4$。

对于100%的数据，$1≤n,a_i≤100,0≤k≤8$。